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

 

문제: "가장 긴 팰린드롬 부분 문자열을 출력하라."

 

팰린드롬 문자는 순서를 거꾸로 읽어도 똑같은 단어였다. 하지만 부분적으로 팰린드롬이 가능한 것들중 가장 긴 것을 찾으라니 머리를 굴리자.

 

팰린드롬의 작은 예를 살펴보면 한글자는 당연히 가능하고, 그 외에는 'aa' 또는 'aba' 에서 시작해나간다. 즉 두글자 'aa'에서 또는 세글자 'aba' 에서 양쪽으로 한칸씩 동일한지 확인해나가면 된다. 이게 투포인터를 사용해서 풀이가 나와있다. 이 투포인터는 두칸짜리와 세칸짜리로 되어 있고 양쪽 끝에 글자가 동일하면 포인터를 좌우로 하나씩 확장시켜주는 역할을 한다. 

 

중첩함수를 사용한다. expand 가 그것인데 for 문에서 i 가 0 인 경우를 생각해보자. expand 안에 left 와 right에다가 0과 1이 들어간다고 생각해보자.

expand 안의 while 문에서 조건이 left가 0보다 커야하고 right 가 전체 길이보다 작아야 하며 결정적으로 두 인덱스의 단어 값이 같아야 반복한다. 반복은 left와 right를 한칸씩 확장시켜 주는 것이다. 그리고 출력은 해당 부분 팰린드롬을 출력하게 해준다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ''
        
        for i in range(len(s) - 1):
            result = max(result, expand(i, i + 1), expand(i, i + 2), key=len)
        
        return result

이 문제는 기본적으로 팰린드롬을 찾기 위해 투 포인터를 홀짝으로 활용한다는 아이디어로 시작해야한다. expand 함수를 사용해서 팰린드롬을 확인하며, 이를 글자개수만큼 반복하는 식이다.

 

짧지만 강력한 알고리즘의 느낌이다. 완벽히 흡수를 시켜야 한다.