[프로그래머스] 가장 긴 팰린드롬 / Python

문제주소 :programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

---

<문제 설명>

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예

s                                                                        answer

abcdcba	7
abacde	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다.

 

<풀이법>

▒ 한줄 개념:  - ▒ 

이번 문제는 특별한 알고리즘이 필요하진 않은 문제입니다. 

문제풀이 방식은 다음과 같습니다.

 

• answer 초기값 1: 1개의 문자열은 무조건 팰린드롬
• O(n)의 반복문을 통해 range(0, len(s)-1) 만큼 반복:  
  • s[i-1] == s[i+1]일 경우: 양쪽으로 퍼져가면서 비교반복
    • ex) 'bab' : i = 1일 경우 조건에 걸림(b == b)
  • s[i] == s[i+1]일 경우: 양쪽으로 퍼져가면서 비교반복
    • ex) 'acca': i = 1일 경우 조건에 걸림(c == c)
  • 각 조건마다 얻어지는 길이값을 answer와 비교하여 더 클 경우 answer값 변경

<반례>

s = 'ddddddd' / result = 7

s = 'dddddddd' / result = 8

 

<코드(Python)>

def solution(phone_book):
    answer = True # 디폴트 True
    phone_book.sort() # 정렬을 통해 연속된 인덱스만 비교
    for i in range(len(phone_book)-1): # 반복문을 통해 비교
        if phone_book[i] in phone_book[i+1]: # 접두어가 되는 번호가 있으면,
            answer = False # False
    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest