[Algorithm][LeetCode][Medium][Python] 5. Longest Palindromic Substring

이 문제도 반 년 전쯤에 풀었던 문제다.

 

복습 겸 내 풀이와 가장 빠른 풀이를 남겨본다.

 

문제는 여기에서 확인해보면 된다.

 

---

 

문제 설명

간단하게 문제를 설명하자면, 한 문자열에서 가장 긴 Palindrome을 찾는 것이다.

 

 

여기서 Palindrome이란, '회문'이라고도 불리며, 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 뜻한다.

 

예를 들면, 'abcba'나 'abba'는 Palindrome이라고 할 수 있다.

 

 

Palindrome인지 확인하는 함수는 Two Pointer 방법이나,

 

파이썬에서는 [::-1]을 이용하면 쉽게 구현할 수 있다.

 

 

내 풀이

코드 먼저 보자.

 

import re

class Solution:
    def isPalindrome(self, s:str) -> bool:
        return s == s[::-1]

    def longestPalindrome(self, s: str) -> str:
        substr = ''
        left_idx = 0
        while left_idx + len(substr) - 1 < len(s):
            right_idx = len(s) - 1
            while not self.isPalindrome(s[left_idx:right_idx+1]):
                right_idx -= 1
            if len(substr) < len(s[left_idx:right_idx+1]):
                substr = s[left_idx:right_idx+1]
            left_idx += 1
        return substr

 

딱 봐도 브루트 포스 느낌.

 

 

주어진 문자열 s에서 한 글자씩 진행하면서 그 때마다의 가장 긴 Palindrome을 찾으려고 했다.

 

그래서 한 글자씩 진행하기 위해 기준이 되는 left_idx라는 변수를 0으로 초기화 시켜 생성했고,

 

substr이라는 가장 긴 palindrome을 저장할 string 변수도 만들었다.

 

 

그리고 매 반복문마다 문자열 s의 가장 오른쪽에서부터 1씩 감소하는 right_idx를 두어

 

문자열 s의 left_idx부터 right_idx까지의 부분 문자열이 Palindrome인지 확인하게 된다.

 

 

엄청 무식한 코드로 짰는데 어찌저찌 돌아가긴 했다.

 

 

 

 

이런 정신나간 퍼포먼스로.

 

 

가장 빠른 코드

이 문제는 Solution이 공짜로 풀려있지만, 성능들이 형편없다.

 

 

Discuss에서 훌륭한 코드를 찾았고, 여기에 들어가면 작성자의 설명과 함께 볼 수 있다.

 

 

이 분은 하나의 가설을 세우고, 그 가설이 옳다는 증명을 한 후, 본인의 코드에 적용했는데 속도가 아래처럼 굉장히 빠르다.

 

 

 

 

그럼 코드를 먼저 보기 전에, 이 코드의 작성자가 사용한 증명법을 간단히 알아보고 넘어가자.

 

 

흔히 귀류법이라고 불리는 모순 증명법인데, 여기에 블로그 주인께서 굉장히 잘 설명해주셨다.

 

간략히 설명하자면, 우리가 옳다고 증명할 하나의 가설1을 세우고

 

가설1과 반대되는(혹은 부합하지 않는) 또다른 가설2를 만들어 증명을 시작한다.

 

가설2에 부합하는 식(혹은 명제 등)을 전개하다 보면 마지막에 가설2에 모순되는 결과가 나온다.

 

그래서 가설1이 맞는 가설임을 증명하게 된다.

 

 

이제 코드를 찬찬히 살펴보자.

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 1:
        	return ""
        maxLen=1
        start=0
        for i in range(len(s)):
        	if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
        		start=i-maxLen-1
        		maxLen+=2
        		continue

        	if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
        		start=i-maxLen
        		maxLen+=1
        return s[start:start+maxLen]

 

이 코드 작성자도 내 풀이처럼 주어진 문자열 s의 가장 왼쪽부터 한 글자씩 진행했다.

 

 

핵심 아이디어가 다른데,

 

'한 글자 진행할 때마다, 이 글자를 포함한 가장 긴 Palindrome의 길이는 최대 2까지만 증가한다'는 것이다.

 

 

위에 걸어놓은 본문 링크에 들어가서 보면, '가장 긴 Palindrome의 길이는 최소 3부터 증가한다' 라는

 

모순 가설을 세워 식을 전개하는데 정말 증명이 된다.

 

 

하여튼 그렇기 때문에 우리는 두 가지 조건문만 고려하면 된다는 것이다.

 

 

우선 maxLen이라는 변수에 가장 긴 Palindrome의 길이를 저장하고 갱신할 것이고,

 

한 글자 진행할 때마다, 해당 글자를 포함하면서

 

1. maxLen+2만큼이 Palindrome인지,

 

혹은

 

2. maxLen+1만큼이 Palindrome인지

 

확인하는 것이다.

 

---

 

한 번 읽어보는 것으로는 코드가 이해 안 갈 가능성이 높다.

 

계속 읽어보고 직접 실행해보면 금방 이해된다.

 

 

끝!