[백준 / BAEKJOON] 1509번 팰린드롬 분할 - Python

문제 원문

조건

시간 제한 : 2초
메모리 제한 : 128 MB

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

예제

풀이

처음엔 백트래킹을 활용한 브루트 포스로 풀어봤으나 역시 시간 초과가 발생합니다.

결국 핵심은 입력받은 문자열에 팰린드롬이 어느 위치에 있는지를 계산하는 것입니다.

예전에 풀었던 문제에서 특정 범위의 문자열이 팰린드롬인지 검사하는 문제가 있어 해당 풀이를 활용하였습니다.

일단 전체 문자열의 팰린드롬 여부를 계산합니다.

그리고 계산된 결과를 활용하여 0번 인덱스부터 입력된 문자열의 크기만큼 최소 분할 개수를 저장하면서 진행합니다.

최소 분할 개수의 계산은 leftIndex부터 rightIndex의 범위의 문자열이 팰린드롬이라면 leftIndex 바로 이전 위치의 최소 분할 개수 + 1이므로 문자열의 크기만큼 전체 탐색하면서 최솟값을 저장하며 진행하였습니다.

풀이과정은 다음과 같습니다.

1. 입력받은 문자열을 전체 탐색하면서 해당 위치부터 팰린드롬이 있는지 탐색하여 범위를 입력하면 팰린드롬인지 확인할 수 있는 배열을 생성합니다.
   팰린드롬을 확인하는 과정입니다.
   1. 0부터 문자열의 크기만큼 순회하는 반복문으로 팰린드롬이 있는지 탐색할 시작 위치를 입력받는다
   2. 시작 위치를 기준으로 홀수인 문자열과 짝수인 문자열이 있으므로 시작 위치를 두 개로 나누어 입력하여 확인한다.
   3. 입력받은 범위는 양쪽 다 1씩 증감하여 해당 인덱스의 문자가 일치하는지 확인하면서 진행하며 문자가 일치하지 않는 경우 바로 종료한다
2. 입력받은 문자열을 왼쪽부터 최소 분할 개수를 계산하면서 진행합니다.
3. right index는 곧 최소 분할 개수를 계산할 문자열의 길이가 됩니다.
4. left index는 0부터 right index까지 탐색하며 left index ~ right index의 문자열이 팰린드롬인지 확인합니다.
5. 팰린드롬이라면 이전에 계산된 [left index - 1] 위치의 값 + 1 과 현재 값을 비교하여 더 작은 값을 저장합니다.

성공 코드

import string
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

inputText = input().rstrip()
answer = int(1e9)
size = len(inputText)

#입력한 위치부터 팰린드롬이 있는지 확인한다
def checkPalindrome(isPalindrome, inputText, startIndex, endIndex):
    size = len(inputText)
    while 0 <= startIndex and endIndex < size and inputText[startIndex] == inputText[endIndex]:
        isPalindrome[startIndex][endIndex] = True
        startIndex -= 1
        endIndex += 1

def getIsPalindrome(inputText):
    size = len(inputText)
    isPalindrome = [[False] * size for _ in range(size)]

    for startIndex in range(size):
        #홀수길이
        checkPalindrome(isPalindrome, inputText, startIndex, startIndex)
        #짝수길이
        checkPalindrome(isPalindrome, inputText, startIndex, startIndex + 1)
            
    return isPalindrome

isPalindrome = getIsPalindrome(inputText)

DP = [1] * size
for rightIndex in range(1, size):
    #초기값은 이전 결과 + 1
    DP[rightIndex] = DP[rightIndex - 1] + 1
    for leftIndex in range(rightIndex):
        #만약 팰린드롬이 있을 경우
        if isPalindrome[leftIndex][rightIndex]:
            #leftIndex가 0일때 팰린드롬인 경우 무조건 최솟값이기 때문에 break
            if leftIndex == 0:
                DP[rightIndex] = 1
                break
            else:
                #현재값과 팰린드롬 이전의 결과+1 중 작은 값을 저장
                DP[rightIndex] = min(DP[rightIndex], DP[leftIndex - 1] + 1)

print(DP[size - 1])

결과

Github - github.com/ledpear