가장 긴 팰린드롬 부분 문자열

가장 긴 팰린드롬 부분 문자열

문제

Given a string s, return the longest palindromic substring in s.
문자열 s가 주어졌을 때, s에서 가장 긴 팰린드롬 부분 문자열을 반환

조건

$1 \le s.length \le 1000$
s consist of only digits and English letters (lower-case and/or upper-case),

예제

Input: babad 
Output: bab

Input: cbbd 
Output: bb

Input: a 
Output: a

Input: ac 
Output: a

Input: xaabacxcabaaxcabaax 
Output: xaabacxcabaax

Input: abbbddedssdeeaaas 
Output: edssde

Input: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Output: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

해결

1st

1 생각

팰린드롬?
- 각 첫부분과 끝부분부터 시작하여 서로 같음
- abba, aba, 가나다라다나가 등
무얼 찾는 건가? 주어진 문자열 중에서 가장 긴 팰린드롬 부분 문자열
- 그럼 부분 문자열의 시작과 끝은?
- 팰린드롬이 된 문자열의 내부는 살펴볼 필요가 없지 않을까?
- 그게 가장 긴 것인지

1 코드

def my_longestPalindrome(self, s: str) -> str:
    ans = ''
    s = "".join(s.split())
    print(s)
    s_len = len(s)
    longestPalindrome = s[0]
    longestPalindromeEnd = s_len - 1
    longestPalindromeMax = 0
    longestPalindromeStart = 0

    for i, c in enumerate(s):
        start = i
        start_old = start
        end = s_len - 1
        end_old = 0
        is_palindrome = False
        is_started = False
        loop_cnt = 0
        if end - start < longestPalindromeMax:
            break 
        
        while start < end:
            first = s[start]
            last = s[end]

            if first != last:
                if is_started:
                    end = end_old
                    start = start_old
                    loop_cnt = 0
                    is_started = False
                    is_palindrome = False
                    longestPalindromeEnd = s_len - 1
                    longestPalindromeStart = 0
                else:
                    end -= 1

                continue
            else :
                if loop_cnt == 0:
                    longestPalindromeStart = start
                    longestPalindromeEnd = end 
                    is_started = True
                    # 다음에 다시 시작할 end 지점
                    end_old = end - 1

                if is_started: 
                    is_palindrome = True
                    loop_cnt += 1
                    start += 1
                    end -= 1

        if is_palindrome:
            if longestPalindromeMax < (longestPalindromeEnd - longestPalindromeStart):
                longestPalindromeMax = longestPalindromeEnd - longestPalindromeStart
                longestPalindrome = "".join(s[longestPalindromeStart:longestPalindromeEnd+1])

    return longestPalindrome

1 결과: 실패

시간 초과 케이스에 걸렸다

2nd

2 생각

첫 번째 시도에서는 양 끝에서 중앙으로 오면서 가장 긴 부분 문자열을 찾으려고 함
어딘가 비효율적이므로 시간 초과. 위의 코드를 고치는 것보다 새로 만드는 게 더 빠를 거 같다
다시 생각을 해보자.
- 목표는?
  - 주어진 문자열(1000자 이하, 숫자와 영문 대소문자) 내에서
  - 가장 긴
  - 팰린드롬인 문자열
- 팰린드롬은?
  - 좌우가 대칭인 문자열
  - 좌우가 대칭이라 하면 자연스럽게 양 끝, 좌와 우에서 좁혀오는 것을 생각하게 된다.
    - 근데 좌/우에서 포인터가 좁혀오는 게 맞을까? 모르겠다
      - 왜 모를까?
    - 최선의 경우는?
      - 주어진 문자열 그 자체가 팰린드롬인 경우다
    - 최악의 경우는?
      - 첫번째 시도 때 발생한 시간 초과 케이스처럼, 좌/우로 쭈욱 같다가 중간쯤 가서 하나 틀린 경우
      - 결국 접어서 중앙을 기점으로 좌/우가 일치하지 않으면 팰린드롬이 아니다
      - 그렇다면 오히려 중앙부터 시작하는 게 최선의 경우를 찾는 데 더 낫지 않을까?
      - 대칭의 의미를 ~~좌와 우가 같다~~가 아니라, 접었을 때 좌/우가 서로 들어 맞다라고 말하자
  - 그렇다면 좌/우 대칭을을 어떻게 파악할 수 있을까?
    1. 앞서 생각한 것처럼 좌 포인터와 우 포인터를 좁혀오는 것
    2. 중앙에서 좌 포인터와 우 포인터를 넓혀 가는 것
      - 여기서 중앙은?
        
        abcdedcba에서는 e
        
        aaaaabaaa에서는 a였다가, 팰린드롬 아니므로 좌 또는 우로 중앙을 이동시킨다
      - 길이가 짝수인 경우? 홀수인 경우?
        
        aba에서 중앙은 b
        
        abccba에서 중앙은? c와 c 사이
      - 문자열 길이에 따라 중앙의 케이스가 다른데 어떻게 처리할까? 원하는 건 좌우로 퍼지면서 대칭을 확인하는 건데…
        
        가운데 문자를 선택해서 먼저 좌/우가 같은지, 다르면 바로 옆과 같은지 체크하자
    3. 아니면 제일 앞에서부터 한 문자를 기준으로 훑어보자

2 코드

def second(self, s: str) -> str:
    ans = ''
    s_len = len(s)
    if s_len == 1:
        return s
    s_sub_palindrome = ''
    s_sub_palindrome_len = 0
    loop_cnt = 0
    # 중앙을 기점으로 하지 말고 제일 앞에서부터 끝까지 모두 훑어보자
    target = s[loop_cnt]
    while loop_cnt < s_len:
        '''
        baaaabb -> baaaab
        baaabb -> baaab
        '''
        print('target: ', target, ', loop_cnt: ', loop_cnt)
        idx_curr = loop_cnt
        # `aba`: 좌/우에 문자 있고 left와 right는 같고 start는 다른 경우
        if idx_curr - 1 >= 0 and idx_curr + 1 < s_len:
            loop_cnt_to_add = 1
            idx_left = idx_curr - 1
            idx_right = idx_curr + 1
            is_palindrome = False
            while idx_left >= 0 and idx_right < s_len:
                if s[idx_left] == s[idx_right]:
                    idx_left -= 1
                    idx_right += 1
                    is_palindrome = True
                else:
                    break
            tmp_len = idx_right - idx_left + 1
            print('[case1] idx_right: ', idx_right, ', idx_left: ', idx_left, 'tmp_len: ', tmp_len, ', sub str: ', s[idx_left:idx_right + 1])
            if is_palindrome and s_sub_palindrome_len < tmp_len:
                s_sub_palindrome_len = tmp_len
                s_sub_palindrome = s[idx_left + 1:idx_right]
                target = s[loop_cnt]

            idx_left = idx_curr
            idx_right = idx_curr + 1
            is_palindrome = False
            while idx_left >= 0 and idx_right < s_len:
                if s[idx_left] == s[idx_right]:
                    idx_left -= 1
                    idx_right += 1
                    is_palindrome = True
                else:
                    break
            
            tmp_len = idx_right - idx_left + 1
            print('[case2] idx_right: ', idx_right, ', idx_left: ', idx_left, 'tmp_len: ', tmp_len, ', sub str: ', s[idx_left:idx_right + 1])
            if is_palindrome and s_sub_palindrome_len < tmp_len:
                s_sub_palindrome_len = tmp_len
                s_sub_palindrome = s[idx_left + 1:idx_right]
                loop_cnt_to_add = 2

            loop_cnt += loop_cnt_to_add
            target = s[loop_cnt]
        else:
            if s_sub_palindrome_len == 0:
                s_sub_palindrome = target
            loop_cnt += 1
            if loop_cnt < s_len:
                target = s[loop_cnt]
    ans = s_sub_palindrome

    return ans

2 결과: 실패

이 경우 bb 케이스에 b만 출력한다

3rd

3 생각

과연 앞서 생각한 조건들이 꼭 필요한 조건들일까?

1. # 시작부터 문자열 범위 체크
if idx_curr - 1 >= 0 and idx_curr + 1 < s_len:
2. # `aba`: 좌/우에 문자 있고 left와 right는 같고 start는 다른 경우
if s[idx_curr - 1] == s[idx_curr + 1] and target != s[idx_curr - 1]:
3. # `abccba`: 이 경우 첫 c에서 비교하고 다음 c는 건너 띄면 되지 않을까?
if target != s[idx_curr - 1] and target == s[idx_curr + 1]:

풀다 보니 위에처럼 일일이 조건을 명시할 필요 없고, 결국 세 케이스다
- abcba처럼 홀수로 팰린드롬인 경우
- abccba처럼 짝수로 팰린드롬인 경우
- 팰린드롬이 아닌 경우
그렇다면, 앞서 시작부터 문자열을 체크하거나, aba 경우, abccba 경우 등을 나눌 필요가 없다.
컴퓨터가 할 것과 내가 할 것을 혼동하지 말자. 경우의 수를 분석해야 하는 것은 맞지만, 그렇다고 모든 경우의 수를 내가 계산하고 있을 필요는 없다

3 코드

def third(self, s: str) -> str:
    print(s)
    ans = ''
    s_len = len(s)
    # 문자열이 1개면 굳이 아래 로직 따를 필요 없다
    if s_len == 1:
        return s

    palindrome_len = 0
    loop_cnt = 0
    # 중앙을 기점으로 하지 말고 제일 앞에서부터 끝까지 모두 훑어보자
    """
    abcddce가 있으면
    a -> False
    b 
        -> abc -> False
        -> bc -> False
    c 
        -> bcd -> False
        -> cd -> False
    d 
        -> cdb -> False
        -> db -> True -> cddc -> True -> bcddce -> while문 벗어남

    """
    target = s[loop_cnt]
    while loop_cnt < s_len:
        # 초기값 설정. 이걸 하지 않으면 아래에서 `ac` 같은 경우 빈 값으로 나온다
        if palindrome_len == 0 and loop_cnt == 0:
            ans = target

        # 20210408: 이전에는 당연했던 코드가 오늘은 생소하다. fourth에서 개선
        # 홀수개인 경우를 훑어 본다
        idx_left = loop_cnt - 1
        idx_right = loop_cnt + 1
        is_palindrome = False
        while idx_left >= 0 and idx_right < s_len:
            print("1. s[{}]: {}, s[{}]: {}".format(idx_left, s[idx_left], idx_right, s[idx_right]))
            if s[idx_left] == s[idx_right]:
                is_palindrome = True
                idx_left -= 1
                idx_right += 1
            else:
                break
        print('1. is_palindrome: {}'.format(is_palindrome))
        if is_palindrome:
            tmp_len = idx_right - idx_left + 1
            if palindrome_len < tmp_len:
                palindrome_len = tmp_len
                # while문 안에서 is_palindrome 체크하고 left 및 right로 이동하므로, 
                # break된 후에는 각각 이전 포인터를 인덱스로 삼아야 한다
                ans = s[idx_left + 1:idx_right]
                print('1. s[{}:{}] = ans: {}'.format(idx_left + 1, idx_right, ans))

        # 짝수개인 경우를 훑어 본다
        idx_left = loop_cnt
        idx_right = loop_cnt + 1
        is_palindrome = False
        while idx_left >= 0 and idx_right < s_len:
            print("2. s[{}]: {}, s[{}]: {}".format(idx_left, s[idx_left], idx_right, s[idx_right]))
            if s[idx_left] == s[idx_right]:
                is_palindrome = True
                idx_left -= 1
                idx_right += 1
            else:
                break
        
        print('2. is_palindrome: {}'.format(is_palindrome))
        if is_palindrome:
            tmp_len = idx_right - idx_left + 1
            if palindrome_len < tmp_len:
                palindrome_len = tmp_len
                ans = s[idx_left + 1:idx_right]
                print('2. s[{}:{}] = ans: {}'.format(idx_left + 1, idx_right, ans))

        loop_cnt += 1
        if loop_cnt < s_len:
            target = s[loop_cnt]
            print("target = s[{}]: {}".format(loop_cnt, target))
        else:
            break

    return ans

3 결과: 성공

Runtime: 760 ms, faster than 90.20% of Python3 online submissions for Longest Palindromic Substring.
Memory Usage: 14.4 MB, less than 63.02% of Python3 online submissions for Longest Palindromic Substring.

다른 사람의 코드

리트코드 결과 중 최단 시간 기록 코드

def longestPalindrome(self, s: str) -> str:
    if len(s) <= 1 or s == s[::-1]:
        return s

    last_successful_length = 1
    last_successful_start = 0

    for right in range(1, len(s)):
        odd_start = right - last_successful_length - 1
        even_start = right - last_successful_length

        odd = s[odd_start:right + 1]
        even = s[even_start:right + 1]

        if odd_start >= 0 and odd == odd[::-1]:
            last_successful_start = odd_start
            last_successful_length += 2
        elif even == even[::-1]:
            last_successful_start = even_start
            last_successful_length += 1

    return s[last_successful_start: last_successful_start + last_successful_length]

hexdigest로 패턴 프린트 해서 출력한 꼼수 외에, 정상적인 코드 중에서 가장 빠른 실행 시간 기록한 코드
짝수, 홀수 구분은 마찬가지지만, 해결 방식이 훨씬 정갈하고, 직관적이고, 심지어 훨씬 빠르다
포인터를 굳이 양쪽으로 펼치지 않고, 오른쪽로만 확장해 나가면서 정순과 역순으로 문자열을 비교한다
- 어차피 문자열 내의 전체 문자를 순회해야 하는 거라면, 굳이 포인터 두 개를 쓸 필요는 없는 거 같다
기록된 실행 시간은 무려 44ms로 내 코드의 약 1/20 실행 시간

프로그래머스에서 가장 간단한 코드

def longest_palindrom(s):
    # 함수를 완성하세요
    return len(s) if s[::-1] == s else max(longest_palindrom(s[:-1]), longest_palindrom(s[1:]))

어처구니 없을 정도로 간단하게 풀었다
가장 긴 팰린드롬에서 확인해야 할 것은 부분 문자열
결국 부분 문자열을 어떻게 확인해나갈 것인가였는데, 이 코드는 재귀적으로 좌/우 하나씩 줄여가며 가장 긴 값을 남기도록 했다.

회고

2 생각에서 대칭에 대해 정리할 때처럼, 설명 방식과 어휘 선택에 따라 문제 해결 방식이 바뀌는 거 같은데, 같은 문제라도 다르게, 다양하게 설명할 줄 알아야 할 것 같다
애초에 좌/우 포인터가 좁혀오는 것, 좌/우 포인터가 넓혀가는 것 이렇게 경우의 수로 나누어서 분기 처리하는 방식으로 사고하는 게 필요할 것 같다
실제 업무에서는 문제 해결을 위해 온갖 방법을 다 생각해내는데, 알고리즘 문제를 풀 때는 문제 자체에 매몰되는 느낌이다. 문제 자체보다는 문제 해결에 집중하자
문제 해결 과정을 상상하자. 기상천외한 방법들을 상상하다 보면 뭐라도 나오지 않을까.
일단 풀었지만, 코드를 작성하는 과정이나 최종적인 결과는 그렇게 매끄럽지 않은 것 같다. 더 풀다 보면 나아지려나