leetcode 5. Longest Palindromic Substring 리트코드 5. 가장 긴 팰린드롬 부분 문자열

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

가장 긴 팰린드롬 부분 문자열

 

입력: 문자열

출력: 문자열

 

문제 요약: 주어진 문자열에서 찾을 수 있는 가장 긴 팰린드롬을 출력하기

유의 사항: 예를 보면 "a", "ac" 가 입력일 때 모두 "a"가 출력되었다. len(a)이 1이거나 같은 팰린드롬이 없을 때는 a[0]이 출력되는 듯

그리고, 문자열 내에 대문자/소문자 모두 들어가 있다고 하니까 .lower()를 통해 모두 소문자로 변환해줘야할 것 같다.

생각 과정

팰린드롬은 뒤집어도 똑같은 값이 나오는 문자열로 이미 AI dev 수업 시간에 프로그래머스 문제로 푼 적도 있고, <파이썬 알고리즘 인터뷰>에도 무려 4문제가 팰린드롬 관련으로 출제될 만큼 프로그래밍 문제 풀이에서 자주 등장하는 개념인 것 같다. 솔직히 내가 혼자서 해결 과정을 짜지는 못했고, 지난 번 문제 풀이를 참고했다. (지난 번 문제도 어려워서 해설을 참고했었다)

 

1. 먼저 팰린드롬 함수를 만든다. 팰린드롬인지 판별하고, 그렇다면 판별하는 구간을 한 칸씩 늘려서 더 긴 팰린드롬인지 확인하는 기능을 한다. 가장 길게 만들 수 있을 때까지 구간을 늘리고, 그 팰린드롬 값을 반환한다.

 

2. 팰린드롬 함수가 들여다 보게 될 순환문을 만든다. 팰린드롬이 문자열의 어느 위치에서 시작할 지 모르기 때문이다. 그리고 팰린드롬이 짝수일 때와 홀수 일 때 들여다 보아야할 최소 단위가 다르므로 (짝수: 2칸, 홀수 3칸) 두 가지 모두를 살펴본다. 짝수, 홀수 조건 모두 그리고 문자열의 모든 가능한 구간을 살펴보고 나서 가장 긴 팰린드롬을(max(key = len)) 반환한다.

 

3. 예외 처리를 고려한다. 이 문제는 두 가지 예외가 있는데,

1) 제시된 문자열 길이가 1이거나, 문자열 자체가 전체 다 팰린드롬인 경우는 문자열 전체를 다시 리턴하면 된다. 이는 팰린드롬 자체가 가지는 특성이다.

2) [a,b] , [a,b,c] 같이 팰린드롬이 없는 문자열이 제시된 경우에는 그 문자열의 첫 번째 글자를 반환한다. 이것은 이 문제에서 특별히 제시한 예외의 경우이다.

 

풀이

지난 문제 풀이 코드를 참고하여, 처음 제출한 코드는 아래와 같았는데, 'wrong answer'가 떴다.

 

def longestPalindrome(s):
    def palindrom(left, right):    
        while left >= 0 and right <= len(s) and s[left] == s[right]:

            left -= 1
            right += 1
        return s[left+1:right]
    result = ""
    if len(s) < 2 or s == s[::-1]:
        return s


    else:
        for i in range(len(s)-2):
            result = max(result, palindrom(i, i+1), palindrom(i, i+2), key = len)
        return result if len(result) > 0 else s[0]

왜 틀렸는지 내역을 봤더니,

 

Input:"ccd"

Output:"c"

Expected:"cc"

 

Input:"abb"

Output:"b"

Expected:"bb"

 

팰린드롬을 제대로 제대로 찾지 못하고 있었다. 그래서 예전에 프로그래머스 문제에 제출했던 답안과 비교해보니,

 

        while left >= 0 and right <= len(s) and s[left] == s[right]:

        while left >= 0 and right < len(s) and s[left] == s[right]:

 

이 부분과, 

        for i in range(len(s)-2):

        for i in range(len(s)-1):

 

이 부분 두 줄이 달랐다. 사실 두 번째 오류는 첫 번째 오류 때문에 생긴 것이었는데, (lens(s) -1) 로 넣으면 list out of range가 떠서 고친 거였기 때문이다.

고쳐서 다시 제출해서 통과된 코드는 다음과 같다.

def longestPalindrome(s):
    def palindrom(left, right):    
        while left >= 0 and right < len(s) and s[left] == s[right]:

            left -= 1
            right += 1
        return s[left+1:right]
    result = ""
    if len(s) < 2 or s == s[::-1]:
        return s


    else:
        for i in range(len(s)-1):
            result = max(result, palindrom(i, i+1), palindrom(i, i+2), key = len)
        return result if len(result) > 0 else s[0]