[Leetcode/파이썬] 5_Longest Palindromic Substring 문제풀이

문제 설명

 

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

 

 

사고 흐름

1. 가장 긴 문자열을 출력해야하니 처음에는 그리디 알고리즘 생각 

2. 근데 s의 입력값 조건이 1000 이하이고, 그리디를 활용한 방법이 떠오르지 않아 완전 탐색으로 방향 잡음

3. 자연스럽게 투포인터 생각 (회문인지 확인하려면 투포인터가 편하니까)

4. 최대 길이 찾는거라서 양쪽 끝에서 시작하면서 모든 경우 비교

 

문제 핵심과 알고리즘

투포인터를 사용해 효율적인 회문 판별 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ''
        for i in range(len(s)-len(ans)) :
            left, right = i, len(s)
            while right>0 and right-left>len(ans) :
                re = s[left:right][::-1]
                if s[left:right] == re and right-left>len(ans) :
                    ans = re
                    break
                right-=1
        
        return ans

 

 

문제 풀면서 헤맸던 부분

딱히 헤맨것은 없지만, 시간 복잡도가 길어서 시간 복잡도를 줄이기 위한 코드를 넣었다.

1. right-left>len(ans)

현재 판별하는 회문의 길이가 최대 길이보다 짧다면 break 

2. for의 range : len(s)-len(ans)

i가 현재 최대 길이(ans)보다 적게 남으면 안되기 때문.. 

 

총평 

예전에는 못 풀었던 문제인데 풀어서 뿌듯하긴 하지만, 너무 비효율적이다. 아래는 모범 답안이다. 내 코드는 실행 시간이 거의 5000ms인데 이 코드는 100ms도 안걸린다.. 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def expand(left, right) :
            while left>=0 and right<len(s) and s[left]==s[right] :
                left-=1
                right+=1
            return s[left+1:right]

        ans = ''
        if len(s)<2 or s==s[::-1] :
            return s
        
        for i in range(len(s)-1) :
            ans = max(ans, expand(i,i+1), expand(i,i+2), key=len)
        return ans

 

기본적인 아이디어 (모든 인덱스에 대해 투포인터 사용해 회문 확인)는 동일하지만,

결정적인 차이점은 나는 '최대 길이를 찾는다'라는 것에 집착해 투포인터를 축소해가면서 회문 판별을 했지만(최대만 찾고 바로 break하니까 훨 더 빠를것이라고 생각함, 하지만 이는 회문이 아닐 경우 끝까지 비교하기 때문에 아주 비효율적임), 위에서는 투포인터를 확장해 가면서 아니면 바로 컷한다. 

문제 풀때는 투포인터에서 방향은 별로 신경안썻는데 이렇게 큰 결과를 가져오다니..

앞으로 투포인터를 사용한다면 확장, 축소 등 방향을 잘 고려해야겠다..