[BOJ] 1509 - 팰린드롬 분할 (Python)

 

 

아이디어

 

부분 문자열들의 팰린드롬 여부를 확인하고 동적 계획법으로 분할 최소 개수를 구해 나간다.

 

 

풀이 #1

 

S의 길이를 N에 저장하고, S의 부분 문자열이 팰린드롬인지 여부를 저장하기 위한 2차원 리스트 is_pal을 만든다.

is_pal[i][j]는 문자열 S의 인덱스 i부터 인덱스 j까지의 부분 문자열이 팰린드롬이면 1, 그렇지 않으면 0을 나타낸다.

 

팰린드롬 분할 최소 개수를 저장하기 위해 0으로 채워진 N+1 길이의 리스트 dp를 만든다.

이후 코드상 인덱스 에러 방지를 위해 문자열 S에서 인덱스 j까지의 팰린드롬 분할 최소 개수는 dp[j+1]에 저장한다.

 

for문은 1부터 시작하므로 is_pal[0][0]과 dp[1]은 for문 실행 전에 저장한다.

길이가 1인 부분 문자열과 바로 앞의 문자와 같은 문자는 is_pal에 1로 저장한다.

 

현재 인덱스까지의 부분 문자열의 팰린드롬 분할 최소 개수 dp[j+1]를 직전 최소 개수 dp[j]에 1을 더한 값으로 저장한다.

for문에서 부분 문자열 시작 부분을 조정하며 현재 인덱스까지의 팰린드롬 여부를 is_pal에 저장한다.

팰린드롬인 문자열이 발견되면 해당 팰린드롬으로 분할했을 때의 분할 최소 개수와 비교해 dp[j+1]을 갱신해 나간다.

 

def solution():
    S = input()
    N = len(S)
    is_pal = [[0]*N for _ in range(N)]
    dp = [0]*(N+1)
    is_pal[0][0] = 1
    dp[1] = 1
    for j in range(1, N):
        is_pal[j][j] = 1
        if S[j-1] == S[j]:
            is_pal[j-1][j] = 1
        dp[j+1] = dp[j]+1
        for i in range(j):
            if is_pal[i+1][j-1] and S[i] == S[j]:
                is_pal[i][j] = 1
            if is_pal[i][j]:
                if dp[i]+1 < dp[j+1]:
                    dp[j+1] = dp[i]+1
    print(dp[-1])

solution()

 

 

내장 함수 min을 사용하는 코드보다 if문으로 비교해 값을 할당하는 코드가 더 빨랐다.

# 1.
dp[j+1] = min(dp[j+1], dp[i]+1)

# 2. 더 빠른 코드
if dp[i]+1 < dp[j+1]:
    dp[j+1] = dp[i]+1

 

 

 

풀이 #2

 

다른 분의 코드를 참고하여 메모리를 더 적게 사용하면서 더 빠른 코드를 작성할 수 있었다.

 

인덱스 접근의 편리를 위해 입력 문자열 S 앞에 문자 하나를 더하고, N에 문자열의 길이를 저장한다.

입력으로 주어질 수 있는 분할 최대 개수인 2500으로 채워진 N 길이의 dp를 생성한다.

 

for문에서 k가 짝수일 때는 홀수 길이의 팰린드롬을, k가 홀수일 때는 짝수 길이의 팰린드롬을 계산한다.

i와 j를 중간으로 하는 부분 문자열의 길이를 문자열 범위를 벗어나지 않는 동안 증가시키면서

해당 팰린드롬으로 분할했을 때의 분할 최소 개수와 비교해 dp[j]의 최솟값을 갱신한다.

 

def solution():
    S = '#'+input()
    N = len(S)
    dp = [2500]*N
    dp[0] = 0
    for k in range(2, N*2-1):
        i, j = k//2, (k+1)//2
        while i > 0 and j < N and S[i] == S[j]:
            if dp[i-1]+1 < dp[j]:
                dp[j] = dp[i-1]+1
            i -= 1
            j += 1
    print(dp[-1])

solution()