[leetcode] 5. 가장 긴 팰린드롬 부분 문자열 (Longest Palindromic Substring)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given a string s, return the longest palindromic substring in s.

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

 

팰린드롬?
거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다.
예를 들어 '수박이 박수'같은 말. 슈퍼주니어의 로꾸거로 많은 사람들이 알고있을 듯.

 

입출력 예시

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

생각과정

만약 "babad" 문자열이 주어졌을 때,
슬라이싱 기법으로 ba, ab, ba, ad / bab, aba, bad / baba, abad / babad로 나눠서 리스트에 담은 다음
각 항목을 일일히 뒤집은 다음에 기존 리스트의 같은 인덱스 데이터와 비교한다음 그 중에서 가장 긴 데이터를 리턴해주고자 했음.
하지만 실패. 해설 코드를 보자.

 

풀이

def expand(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        # 투 포인터 확장
        # ex) left = 0, right = 0 + 1 일 때, s[left] = b, s[right] = a 이므로 포인터를 확장하지 않고 s[1:1]인 빈 값을 반환함
        # left = 1, right = 1 + 2 일 때, s[left] = a, s[right] = a 이므로 포인터를 확장시킨다.
        # 확장시키고 나면 s[left] = 0, s[right] = 4이고, s[left] = b, s[right] = d이므로 s[1:4]인 'ab'를 반환시킨다.
        left -= 1
        right += 1
    return s[left + 1:right]


# 해당 사항이 없을 때, 빠르게 리턴
if len(s) < 2 or s == s[::-1]:  # s[::-1] -> 문자열을 역순으로 배열
    print(s)

result = ''

# 슬라이딩 윈도우 우측으로 이동
# range(len(s) - 1) -> s의 길이가 5일 때, 최소 2글자가 출력되려면 s[4:5]이므로 i의 최대값은 len(s) - 1 이다.
for i in range(len(s) - 1):
    result = max(result,
                 expand(i, i + 1),  # 짝수일 때
                 expand(i, i + 2),  # 홀수일 때
                 key=len)

return result

 

추후에 그림도 추가하겠음

 

우선, 속도를 위해서 팰린드롬에 해당하지 않는 1자리 문자열이거나, 앞뒤를 뒤집어도 똑같지 않은 문자열은 빠르게 리턴해준다.

 

리턴할 result를 생성해준 후, for문으로 모든 경우의 수를 비교한다.

for문의 조건에서 왜 문자열 길이에 1을 빼는가 했더니, 리턴되야하는 최조 팰린드롬 문자열은 2글자이기 때문이었다.

 

문제에서는 가장 긴 팰린드롬 문자열을 리턴하라고 했기 때문에 max함수를 사용하였고, 여기서 '투포인터'라는 개념이 등장한다.

해설에서 사용한 '투포인터'라는 개념은 그림이 없으면 이해하기 매우 어려움으로 관련 글을 추가하겠다.

 

투포인터 알고리즘

GitHub - WooVictory/Ready-For-Tech-Interview: 💻 신입 개발자로서 준비를 하기 위해 지식을 정리하는 공간

 

 

코드에서 expand 함수는 투포인터를 가운데에서부터 점차 확장시켜나가며 비교하는 방식을 선택했다.

역시나 이 부분이 이해하기 너무나 어려워서 예시로 직접 값을 넣어가며 이해했는데, 아래를 보자

 

투 포인터 확장
ex) left = 0, right = 0 + 1 일 때, s[left] = b, s[right] = a 이므로 포인터를 확장하지 않고 s[1:1]인 빈 값을 반환함
left = 1, right = 1 + 2 일 때, s[left] = a, s[right] = a 이므로 포인터를 확장시킨다.
확장시키고 나면 s[left] = 0, s[right] = 4이고, s[left] = b, s[right] = d이므로 s[1:4]인 'aba'를 반환시킨다.

 

여기서 return값이 s[left + 1: right]인 이유는 while문을 쭉 돌렸을 때, 조건에 일치하면 다음 조건을 확인하기 위해 한번 더 while을 반복한다. 만약 그대로 left와 right를 리턴한다면 원하는 값보다 한칸 더 확장된 결과값을 리턴하게 되니까, 슬라이싱의 왼쪽 인덱스는 원하는 인덱스인 left + 1을, 오른쪽 인덱스는 어차피 -1이 된 값을 찾아주기 때문에 right로 지정해서 리턴하는 것.

 

최종적으로 해당 함수가 끝이 나게 되면 원래 코드로 넘어오게 되는데 여기서 궁금한게 하나 더 생긴다

 

i + 1과 i + 2 차이가 뭐에요?

    result = max(result,
                 expand(i, i + 1),  # 짝수일 때
                 expand(i, i + 2),  # 홀수일 때
                 key=len)

 

팰린드롬은 aba처럼 홀수일 수도 있고, baab처럼 짝수일 수도 있다.

홀수이면 가운데 b는 남겨두고 좌우로 확장하고, 짝수이면 aa를 기준으로 확장해야하기 때문이다!

 

 

이렇게 모든 코드를 돌고, 함수에서 리턴된 값들 중 가장 큰 값을 return해주면 해결!

---

마치며

너무 헷갈려서 정말 많은 시간이 걸린 문제이다.

팰린드롬 문제는 매우 자주 출제된다고 하니, 투포인터의 개념을 확실히 익히고 넘어가자.