Leetcode 5. Longest Palindromic Substring - Python (cf. 백준 13275)

 

Leetcode 5 문제 보기

 

문제 이해하기

주어진 문자 s의 substring 중에서 가장 긴 팰린드롬인 substring을 찾아라.

즉, 뒤집어도 같아지는 (eg. 토마토) 부분문자열을 출력하라.

(1 <= s.length <= 1000)

 

아이디어 구상

팰린드롬이란 결국 "가운데를 기준으로 대칭인 문자"를 의미한다.

때문에 주어진 s의 각 문자들을 기준으로 양 옆으로 물결이 퍼져나가듯 검사를 하면서 팰린드롬 여부를 검사할 수 있게 된다.

이 경우 s의 각 문자들을 기준으로 삼기 위한 탐색 O(n)과 각각의 기준 문자에 대해 투 포인터를 활용해 좌우 검사를 진행하기 위한 O(n), 총 O(n^2)의 시간복잡도를 가지게 된다.

 

By Mesotes

 

탐색을 진행할 때 유의할 점은, 정답인 부분문자열이 짝수 혹은 홀수 개의 문자로 구성될 수 있다는 점이다.

때문에 홀수일 경우 기준을 하나의 문자로 하고, 짝수일 경우 기준을 두 개의 문자로 해야한다.

코드를 보면 이해가 더 쉬울 것으로 생각된다.

 

풀이

정답을 담을 res와 res의 길이 max_length를 선언한다.

res = ""
max_length = 0

 

이후 for문을 돌며 주어진 s에서 하나의 문자를 기준으로 탐색을 진행한다.

for i in range(len(s)):

 

그리고 substring이 홀수 개의 문자로 이루어진 경우를 생각해보면, left와 right 포인터가 같은 위치, 즉 기준 문자에서부터 시작해 양 옆으로 퍼져나가면 된다.

left, right = i, i
while left >= 0 and right < len(s) and s[left] == s[right]:
    temp_length = right - left + 1
    if temp_length > max_length:
        res = s[left:right + 1]
        max_length = temp_length
    left -= 1
    right += 1

짝수 개일 경우 두 개의 연속된 문자들을 기준으로 퍼져나가자.

left, right = i, i + 1
while left >= 0 and right < len(s) and s[left] == s[right]:
    temp_length = right - left + 1
    if temp_length > max_length:
        res = s[left:right + 1]
        max_length = temp_length
    left -= 1
    right += 1

 

전체 코드는 다음과 같다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        max_length = 0

        for i in range(len(s)):
            # odd length substring
            left, right = i, i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                temp_length = right - left + 1
                if temp_length > max_length:
                    res = s[left:right + 1]
                    max_length = temp_length
                left -= 1
                right += 1
            
            # even length substring
            left, right = i, i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                temp_length = right - left + 1
                if temp_length > max_length:
                    res = s[left:right + 1]
                    max_length = temp_length
                left -= 1
                right += 1
        
        return res

---

그런데 아직 뭔가 아쉽다.

홀수 개일때와, 짝수 개일 때.

저 두 중복된 코드가 보이는가.

하나로 묶을 수 있을 것 같다.

def validate(left: int, right: int) -> str:
    res = ""
    max_length = 0
    while left >= 0 and right < len(s) and s[left] == s[right]:
        if (right - left + 1) > max_length:
            res = s[left:right + 1]
            max_length = right - left + 1
        left -= 1
        right += 1
            
    return res

 

이렇게 매번 s[left:right + 1]하는 것은 비용이 크다.

때문에 탐색 순간마다 슬라이싱을 하지 않고 max_length와 더불어 left, right를 리턴, 최종적으로 얻어진 left와 right 포인터를 통해 답을 출력할 때만 문자열 슬라이싱을 진행하자.

def validate(left: int, right: int) -> tuple:
    max_length = 0
    while left >= 0 and right < len(s) and s[left] == s[right]:
        if (right - left + 1) > max_length:
            max_length = right - left + 1
        left -= 1
        right += 1
        
    return (left + 1, right - 1, max_length)

 

추가적으로 주어진 문자열 s가 단일 문자이거나, 그 자체로 팰린드롬이라면 불필요한 for문 탐색을 진행할 필요가 없겠다.

해당 조건을 추가해 탐색 과정을 효율화하자.

if len(s) < 2 or s == s[::-1]:
    return s

 

이렇게 개선된 전체 코드는 다음과 같다.

처음의 코드에 비해 Runtime이 2496 ms에서 200 ms로 91%가량 단축됐다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = (0, 0, 0)

        # base case
        if len(s) < 2 or s == s[::-1]:
            return s

        # validate function
        def validate(left: int, right: int) -> tuple:
            max_length = 0
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if (right - left + 1) > max_length:
                    max_length = right - left + 1
                left -= 1
                right += 1
            
            return (left + 1, right - 1, max_length)
        
        for i in range(len(s)):
            res = max(res, validate(i, i + 1), validate(i, i + 2), key = lambda x:x[2])

        return s[res[0]:res[1] + 1]

---

백준 13275번 문제는 위와 거의 동일한 문제다.

백준 13275 문제 보기

 

문제 이해하기

이번에는 부분문자열 그 자체가 아닌, 부분문자열의 길이를 출력한다.

다만 주어지는 문자 s의 길이가 1000까지가 아닌 10만까지로 더 길다.

 

아이디어 구상

길이를 출력하도록 약간 손을 본 전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline

# initialize
s = input().strip()
res = 0

# validate function
def validate(left: int, right: int) -> int:
    max_length = 0
    while left >= 0 and right < len(s) and s[left] == s[right]:
        if (right - left + 1) > max_length:
            max_length = right - left + 1
        left -= 1
        right += 1
            
    return max_length

# base case
if len(s) < 2 or s == s[::-1]:
    print(len(s))

else:
    for i in range(len(s)):
        res = max(res, validate(i, i), validate(i, i + 1))
    print(res)

 

문제는 시간초과가 나온다는 것.

PyPy3로 제출 시 다행히 통과되지만, CPython으로는 시간이 초과된다.

 

코드를 더 효율화시킬 방안이 없을까 찾아보다가 Manacher 알고리즘을 접하게 됐다.

Manacher 알고리즘은 쉽게 말해 "굳이 검사할 필요 없는 기준 문자는 건너뛰고 검사를 속행하는 방법"이다.

 

우선 bnanxnanc라는 문자를 예시로 팰린드롬에 있어 "반지름"의 개념에 대해 알아보자.

1. 가장 첫 번째 문자 b의 경우, 좌측에 더이상 문자가 없으므로 팰린드롬의 반지름은 0이다.

2. 두 번째 문자 n의 경우에도, 좌우의 문자가 다르므로 팰린드롬은 자기자신, 즉 팰린드롬 반지름은 0이다.

3. 세 번째 문자인 a의 경우, 양 옆에 n이 동일하다. 때문에 팰린드롬 반지름은 1이다.

4. 네 번째 문자인 n의 경우, 반지름은 0이다.

따라서 문자 bnanxnanc에 대한 팰린드롬 반지름을 array로 표현하면 다음과 같이 나타낼 수 있다.

radius = [0, 0, 1, 0, 3, 0, 1, 0, 0]

 

그렇다면 현재 기준 문자가 5번째 문자인 x라고 해보자.

다음 검사해야할 기준 문자는 6번째 문자인 n일까?

그렇지 않다. 팰린드롬의 특성에 의해 6번째 문자는 4번째 문자와 대칭이며 그 반지름이 0일 것이기 때문이다.

그렇다면 7번째 문자인 a는 어떤가?

검사해야한다. 왜냐하면 3번째 문자인 a의 경우 그 반지름이 1이며, 이는 x를 기준으로 한 팰린드롬의 끝 문자에 맞닿아 있기 때문이다. 즉, 7번째 문자인 a에서부터 양 옆으로 펼쳐나가며 검사를 진행하게 되면 "5번째 문자인 x를 기준으로 한 팰린드롬보다 더 긴 팰린드롬이 존재할 가능성"이 있기 때문에 검사를 진행해야 한다.

 

설명을 읽자니 복잡하다.

Manacher 알고리즘에 대해 친절히 설명한 좋은 영상과 글이 있어 첨부한다.

Manacher's Algorithm | Longest Palindromic Substring

Longest palindromic substring - Wiki

 

풀이

한편, Manacher 알고리즘은 기준 문자 하나에 대한 검사만 가능하다.

때문에 짝수 개의 문자로 이루어진 substring을 판별하기 위해서 약간의 트릭이 필요하다.

각 Character 사이사이에 임의의 특수문자(주어진 s에는 포함되지 않는)를 삽입해 검사를 진행하고, 이후 정답 출력 시 특수 문자를 다시 제외하면 깔끔하게 구할 수 있다.

 

전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline

def manacher(s):
    radius = [0 for i in range(len(s) + 1)]  # palindrome radius
    norm = 0  # index of norm character
    max_radius = 0  # maximum radius of palindrome so far
    
    for i in range(1,len(s) - 1):
        if i < max_radius:
            radius[i] = min(max_radius - i, radius[2 * norm - i])
        else:
            radius[i] = 1
        while s[i - radius[i]] == s[i + radius[i]]:
            radius[i] += 1
        if max_radius < i + radius[i]:
            norm = i
            max_radius = i + radius[i]
    norm, max_radius = 0,0
    for i in range(len(s)):
        if max_radius < radius[i]:
            norm = i
            max_radius = radius[i]
    return len(s[norm - radius[norm] + 1:norm + radius[norm]].replace('#',''))

s = input().strip()
print(manacher('$#' + '#'.join(s) + '#@'))

---

Leetcode 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/​

 

백준 13275. 가장 긴 팰린드롬 부분 문자열 (플래티넘 5)

https://www.acmicpc.net/problem/13275​

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다