[백준] 팰린드롬 분할

https://www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

다이나믹 프로그래밍을 두번 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 주어진 문자열에 팰린드롬 분할을 한 갯수의 최솟값을 출력해야 합니다. 

 

처음에 두개의 다이나믹 프로그래밍중 하나만 이용하여 시간초과가 났었고 이후에 해결을 하였는데 각각 과정들을 한번 설명해 보겠습니다. (큰 아이디어에서 출발해서 수정을 한 부분의 아이디어도 함께 설명하려 합니다.)

 

<Solution>

우선 이 문제의 큰 아이디어는 다음과 같습니다. 

1. 어떤 string s에 대해 뒤에서 부터 펠린드롬인 부분들을 찾습니다. (이렇게 찾은 펠린드롬의 길이를 p,q,r 라고 가정해 봅시다.) 2. dp array를 dp[i] = 처음부터 i번째 문자까지 펠린드롬 분할의 최솟값 으로 정의하였을 때, 특정 k에 대해서 dp[k] = min(dp[k-p],dp[k-q],dp[k-r]) + 1 이 됩니다.

간단한 예시로 설명을 해보겠습니다. 

 

ABACABA라는 string이 있다고 생각해봅시다. 

이 때, 우리가 dp[7] 즉 ABACABA의 전체 펠린드롬 분할의 최소 횟수를 구해야 하면 어떻게 해야할까요?

 

뒤에서 부터 펠린드롬인 부분들을 찾아봅니다.

• A는 펠린드롬입니다.(길이 = 1)
• ABA는 펠린드롬입니다.(길이 = 3)
• ABACABA는 펠린드롬입니다.(길이 = 7)

그렇다면 이제 위에서 정의한 dp의 정의를 활용하면, 우리는 이 dp[7]을 

dp[7] = min(dp[7-1], dp[7-3], dp[7-7]) + 1

이렇게 정의할 수 있습니다. 즉 ABACAB의 펠린드롬 분할의 최소횟수 + 1과 ABAC의 펠린드롬 분할의 최소횟수 + 1 과 빈 문자열의 펠린드롬 분할의 최소횟수 + 1(-> 0+1)중 더 작은 값이 정답이 되는 것을 알 수 있습니다. 

 

실제로 처음에는 이 방식을 이용하여 구현을 하였습니다. 하지만 시간 초과가 발생하는 것을 알 수 있었습니다. 

[Time out이 발생한 코드]

import sys

s = sys.stdin.readline().rstrip()

dp = [0 for _ in range(len(s)+1)]
dp[1] = 1

def palindrome_reverse(s):
    # find palindrome from reverse order
    ret = []
    s_ = "".join(reversed(s))
    index_odd = len(s)//2 + len(s)%2
    index_even = len(s)//2
    flag = 0
    length1 = 0
    # odd 
    # print(f'index_odd, index_even = {index_odd, index_even}')
    for i in range(index_odd):
        i_ = i+1
        for j in range(i_):
            if s_[i-j] != s_[i+j]:
                flag = 1
                break
        if flag == 1:
            flag = 0
            continue
        length1 = 2*i+1
        ret.append(length1)
    # even
    flag = 0
    length2 = 0
    for i in range(index_even):
        i_ = i+1
        total_len = 2*(i_)
        for j in range(i_):
            if s_[j] != s_[total_len-1-j]:
                flag = 1
                break
        if flag == 1:
            flag = 0
            continue
        length2 = 2*(i+1)
        ret.append(length2)
    return ret

def solution(s):
    for i in range(2, len(s)+1):
        ret = palindrome_reverse(s[:i])
        tmp = int(2e9)
        for e in ret:
            tmp = min(tmp, dp[i - e])
        dp[i] = 1 + tmp

    return dp[len(s)]

print(solution(s))

 

이 과정에서 줄일 수 있는 부분이 있습니다.

 

뒤에서 부터 펠린드롬을 찾는 과정은 같은 연산이 계속 반복되는 것을 알 수 있습니다. 이러한 과정을 줄이기 위해 is_palindrome이라는 array를 하나 더 두어서 해결하였습니다. 

is_palindrome = [[False] * len(s) for _ in range(len(s))] 
# if is_palindrome[0][k] = True string[0] ~ string[k] is palindrome

이 is_palindrome array는 string의 두 index사이의 string이 palindrome인지를 판단해 줍니다.

 

즉 ABA라는 문자열을 예시로 설명하면, is_palindrome[0][2] = True고, is_palindrome[1][2] = False가 될 것 입니다. (ABA는 palindrome이 맞으므로 True, BA는 palindrome이 아니므로 False) 

 

그렇다면 이 array를 채워나가 봅시다. 길이가 1, 2, 3 이렇게 증가하는 순서대로 채워나갈 예정입니다. 이렇게 하면 중복되는 searching을 줄일 수 있습니다. 

* 과정을 자세히 아래에서 살펴봅시다.

1. 길이가 1인 string들을 모두 True입니다. 
2. 길이가 2인 string들은 비교를 해서 직접 True False를 판단해줍니다.
3. 이후의 길이들은 만약 길이가 k라고 생각해보면, (string을 s라고 가정)
   is_palindrome[i][i+k-1] = is_palindrome[i+1][i+k-2] and s[i][i+k-1]

이러한 과정을 통해 계산이 가능합니다. 

 

간단한 예시로 설명을 덧붙이자면, s = "ABA" 의 palindrome여부는 is_palindrome[0][2] 입니다.

is_palindrome[1][1] == True 즉 "B" 는 palindrome이 맞으므로, 이제 s[0] 과 s[2]를 비교해줍니다. 둘다 "A"로 동일하므로 palindrome이 맞다고 판단할 수 있습니다. 

 

이제 실제 구현은 아래와 같습니다. 

[정답 코드]

import sys

s = sys.stdin.readline().rstrip()

is_palindrome = [[False] * len(s) for _ in range(len(s))] 
# if is_palindrome[0][k] = True string[0] ~ string[k] is palindrome
# length 1 as true
for i in range(len(s)):
    is_palindrome[i][i] = True

for i in range(2, len(s) + 1):
    total_search_time = len(s) + 1 - i
    if i == 2:
        for j in range(total_search_time):
            if s[j] == s[j+1]:
                is_palindrome[j][j+1] = True
    else:
        for j in range(total_search_time):
            is_palindrome[j][j+i-1] = is_palindrome[j+1][j+i-2] and s[j] == s[j+i-1]

dp = [0 for _ in range(len(s)+1)]
dp[1] = 1

def palindrome_reverse(s):
    ret = []
    # find palindrome from reverse order
    dp_end_index = len(s) -1
    for i in range(dp_end_index+1):
        if is_palindrome[i][dp_end_index]:
            ret.append(dp_end_index-i+1)
    return ret


def solution(s):
    for i in range(2, len(s)+1):
        ret = palindrome_reverse(s[:i])
        tmp = int(2e9)
        for e in ret:
            tmp = min(tmp, dp[i - e])
        dp[i] = 1 + tmp

    return dp[len(s)]

print(solution(s))