[프로그래머스] 가장 긴 팰린드롬

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 가장 긴 팰린드롬

새로 알게된 것들

문제를 시간초과로 통과하지 못할 것 같은 풀이도 일단 코드를 짜보고 판단하자. 그냥 반복문으로 완전탐색하면 시간초과가 날거 같아 시도조차 해보지 않았는데 정답이였다...

풀이 1

완전탐색으로 풀리지 않을 것 같아 처음에는 동적계획법으로 풀어보았다.

1. 메모이제이션을 해줄 cache 이차원 리스트를 초기화해준다.

2. cache가 0이 아니라면 다른 값에 의해 초기화가 된 것이기 때문에 더 이상 구할 필요가 없기 때문에 바로 반환해준다.

3. 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 더 이상 탐색을 해볼 필요가 없기 때문에 두 인덱스의 차이를 반환해준다.

4. 만약 두 인덱스에 해당하는 문자가 같을 경우 바로 cache에 +2를 해주지 않는다. 이유는 이 문자열이 팰린드롬이 될지 아직 모르기 때문이다. 그래서 find_palindrome(left + 1, right - 1) == right - left - 1을 하여 팰린드롬인지 확인하고 맞다면 두 인덱스의 차이를 cache에 초기화해준다.

5. 두 인덱스에 해당하는 문자가 다를 경우는 왼쪽 인덱스를 +1하는 경우와 오른쪽 인덱스를 -1하는 경우 두가지로 find_palindrome(left + 1, right), find_palindrome(left, right - 1)을 해주어 꼼꼼히 탐색해준다.

코드

import sys
sys.setrecursionlimit(10**6)

def solution(s):
    n = len(s)
    cache = [[0 for _ in range(n)] for _ in range(n)]
    def find_palindrome(left, right):
        if cache[left][right] != 0: return cache[left][right]
        if left >= right: return right - left + 1
        if s[left] == s[right] and find_palindrome(left + 1, right - 1) == right - left - 1:
            cache[left][right] = right - left + 1
        cache[left][right] = max(
            cache[left][right],
            find_palindrome(left + 1, right),
            find_palindrome(left, right - 1)
        )
        return cache[left][right]
    
    answer = find_palindrome(0, n - 1)
    return answer

풀이 2

모든 경우를 모두 탐색하였다.

1. (0, 1), (0, 2), ... (0, n) ... (n - 1, n) 다음과 같은 순서쌍을 이중for문을 이용해서 만들어준다.

2. 1번에서 만든 순서쌍을 그대로 리스트 슬라이싱하고 뒤집은 문자열과 같은지 비교하고 최대값을 초기화한다.

코드

def solution(s):
    n = len(s)
    answer = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            if s[i:j] == s[i:j][::-1]:
                answer = max(answer, j - i)

    return answer