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

링크 : https://school.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

 📝 코드

def solution(s):
    # 팰린드롬을 판별하여 팰린드롬이 맞다면 가장 긴 팰린드롬을 위해 left, right를 조정하여 확장한다.
    def expand(left, right):
        while left >= 0 and right < len(s)  and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]
    
    # 문자열의 길이가 2보다 작거나 문자열이 이미 팰린드롬을 만족했을 경우
    if len(s) < 2 or s == s[::-1]: 
        return len(s)
    
    answer = ''
 
    # 오른쪽으로 이동하면서 들어온 문자열이 팰린드롬일 경우 확장
    for i in range(len(s)-1):
        answer = max(answer, expand(i,i+1), expand(i,i+2), key = len)   # 짝수와 홀수의 경우를 나눠서 봐야함
    return len(answer)

- 홀수인 경우 (i ,i+i)  : bab 

- 짝수인 경우 (i, i+2): bb

i	i+1	i+2	i+3	i+4
b	a	b	a	b

오른쪽으로 이동하면서 들어온 문자열이 팰린드롬일 경우 확장

i	i+1	i+2	i+3	i+4	i+5	i+6
2	3	4	5	4	3	2