[알고리즘 문제 풀이] 가장 긴 팰린드롬 부분 문자열

문제

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

---

예제1

입력

"babad"

출력

"bab"

예제2

입력

"cbbd"

출력

"bb"

---

이 문제는 다이나믹 프로그래밍을 이용한 풀이도 가능하지만 직관적인 이해가 어렵고, 실행 속도가 늦다. 따라서 여기서는 훨씬 더 성능이 좋은 투 포인터가 중앙을 중심으로 확장하는 형태로 풀이해본다. 팰린드롬 판별만 하면 되기 때문에 앞, 뒤 문자가 같을 때 중앙을 중심으로 점점 확장해 나가면서 가장 긴 팰린드롬을 판별하는 알고리즘을 구현해본다.

알고리즘의 진행 순서는 다음과 같다.

1. 원본 문자열과 뒤집은 문자열이 동일한 경우(aba, 131 등등...)나 문자열의 길이가 1 이하인 경우는 들어온 문자열을 그대로 리턴
2. 길이가 2인 포인터를 전진하며 팰린드롬 찾기
3. 길이가 3인 포인터를 전진하며 팰린드롬 찾기
4. 문자열의 끝에 도달할 때까지 2, 3번 과정을 반복하며 진행하고 결과를 리턴

조건을 하나씩 따져보자면 만약 s에 "aba"가 들어오게 된다면, 1번 조건에 걸려서 2,3 과정은 진행하지 않고 바로 리턴하게 된다.

또한, s에 "ㅎ"이 들어오게 된다면 앞과 뒤를 따져볼 것도 없으므로 그냥 리턴하게 된다.

이 두 과정을 넘기게 된다면 반복문에 진입해서 길이가 2인 포인터와 길이가 3인 포인터를 문자열의 끝에 다다를 때까지 전진하며 팰린드롬인지를 판별하게 된다. 이를 계속해서 result에 담아주고 현재까지의 결과와 이후 결과의 길이를 비교한 뒤 길이가 가장 긴 것(key=len)을 결과 값으로 리턴하게 된다. 

 

전체 코드는 다음과 같다.

# input: "babad"
# output: "bab"

# input: "cbbd"
# output: "bb"

def longestPalindrome(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 s == s[::-1] or len(s) < 2:
        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

s = "babad"
print(longestPalindrome(s))

---

알게된 점

팰린드롬을 판별할 때 포인터를 확장하는 방법

max 함수의 인자값으로 key=len으로 하여 길이가 가장 긴 것을 리턴받는 방법

 

공부할 것

슬라이딩 윈도우를 활용한 문제 또는 팰린드롬에 대한 문제 풀이