P.1509 팰린드롬 분할

코드

import java.io.*;
import java.util.Arrays;

public class Main {

    static String[] str;
    static int len;
    static boolean[][] isPalindrome;

    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine().split("");
        len = str.length;
        isPalindrome = new boolean[len + 1][len + 1];

        for (int i = 0; i < len; i++) {
            for(int j = 1; j + i <= len; j++) {
                if (i == 0) isPalindrome[j][j] = true;
                else if (checkPalindrome(j, j + i)) isPalindrome[j][j + i] = true;
                else isPalindrome[j][j + i] = false;
            }
        }

        dp = new int[len + 1];
        Arrays.fill(dp, len);
        dp[0] = 0;
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= i; j++) {
                if (isPalindrome[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
            }
        }

        bw.write(Integer.toString(dp[len]));
        bw.flush();
    }

    private static boolean checkPalindrome(int start, int end) {
        if (str[start - 1].equals(str[end - 1])) {
            if (end - start == 1 || isPalindrome[start + 1][end - 1]) return true;
        }
        return false;
    }
}

코드 설명

이해를 잘 못해서 시간이 많이 걸린 문제였다.

이해가 가지 않은 부분은 두 가지였다.

 

1. 분할한 것이 모두 팰린드롬이어야하나?

2. 분할한 것의 개수를 세는 것인가 집합의 개수를 세는 것인가?

 

예시를 뜯어보느라 시간이 많이 걸렸는데 다음을 구하는 것이 정답이었다.

팰린드롬인 문자열을 가진 집합 중 부분문자열의 수가 가장 적은 것의 개수

 

이제 문제를 풀기 위해 두 가지를 구해야 한다.

1. 부분 팰린드롬을 모두 구한다.
2. 부분문자열의 수가 가장 적은 것을 구한다.

 

1. 부분 팰린드롬 구하기

for (int i = 0; i < len; i++) {
    for(int j = 1; j + i <= len; j++) {
        if (i == 0) isPalindrome[j][j] = true;
        else if (checkPalindrome(j, j + i)) isPalindrome[j][j + i] = true;
        else isPalindrome[j][j + i] = false;
    }
}

private static boolean checkPalindrome(int start, int end) {
    if (str[start - 1].equals(str[end - 1])) {
        if (end - start == 1 || isPalindrome[start + 1][end - 1]) return true;
    }
    return false;
}

1) 길이가 1일 경우, 팰린드롬이다.

2) 길이가 2일 경우, 두 글자가 같으면 팰린드롬이다.

3) 길이가 3이상일 경우, 첫 글자와 마지막 글자가 같고 (첫 글자 + 1) ~ (마지막 글자 - 1)이 팰린드롬이면 팰린드롬이다.

 

Bottom-Up 방식으로 풀어야하기 때문에 길이가 짧은 것부터 먼저 쌓아 올라가야한다.

 

ABACABA일 때, isPalindrome 배열은 다음과 같다.

1	0	1	0	0	0	1
0	1	0	0	0	1	0
0	0	1	0	1	0	0
0	0	0	1	0	0	0
0	0	0	0	1	0	1
0	0	0	0	0	1	0
0	0	0	0	0	0	1

파란색 1은 길이가 1인 부분문자열이다.

 

idx 1~3일 때 부분문자열은 ABA이며 양 끝 글자가 A로 같고 isPalindrome[1 + 1][3 - 1] == isPalindrome[2][2] == true이기 때문에 isPalindrome[1][3] = true이다.

 

idx 1 ~ 7일 때 부분문자열인 ABACABA가 팰린드롬인지 확인하는 과정은 다음과 같다.

1) 양 끝 글자가 A로 같고 idx 2~6인 부분문자열이 팰린드롬인지 확인한다.

2) idx가 2~6일 때, 양 끝 글자가 B로 같고 idx 3~5인 부분문자열이 팰린드롬인지 확인한다.

3) idx가 3~5일 때, 양 끝 글자가 A로 같고 idx 4~4인 부분문자열이 팰린드롬인지 확인한다.

4) idx가 4일 때, 길이가 1인 부분문자열이므로 팰린드롬이다.

 

코드 내에서는 Bottom-Up과정이기 때문에 4 -> 3 -> 2 -> 1순서로 확인된다.

 

2. 부분문자열의 수가 가장 적은 것 구하기

dp[n] = n까지의 문자열 중 부분문자열의 수가 가장 적은 것의 개수

일단 조건은 부분문자열에 팰린드롬 문자열이 포함되어야 한다.

 

만약 ABACABA에서 ABA까지 팰린드롬이므로 dp[3]이 1이라고 가정해보자.

dp[4]는 4번째까지의 문자열 중 부분문자열 개수의 최솟값을 구하게 되는데 str[4]는 한 글자이므로 팰린드롬이며, dp[3]까지의 최솟값은 1이므로 dp[4] = n{'ABA', 'C'} = 2이다.

 

즉, n번째 수가 팰린드롬이라면 n - 1번째까지 결과값에 + 1을 더한다.

하지만 n번째까지의 수를 보기 위해서는 (1, 2~n), (1~2, 3~n) ... (1~n - 1, n)처럼 다양한 방법이 있으므로 그 중에서 최솟값을 찾아야하므로 min함수를 이용한다.

dp[n] = min(dp[n], dp[n - 1] + 1)

dp = new int[len + 1];
Arrays.fill(dp, len);
dp[0] = 0;
for (int i = 1; i <= len; i++) {
    for (int j = 1; j <= i; j++) {
        if (isPalindrome[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
    }
}