[BOJ] 1509 : 팰린드롬 분할(Java)

문제 링크

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

1509번: 팰린드롬 분할

---

💡 풀이

기존 팰린드롬 문제와 다이나믹 프로그래밍을 함께 사용하는 문제입니다.

로직은 다음과 같습니다. 

1. 문자열의 i번째까지 탐색했을 때의 분할 개수의 최솟값을 `dp[i]`로 나타내겠습니다. 이 `dp[]` 배열 활용해 다이나믹 프로그래밍을 진행합니다.
2. 맨 오른쪽 즉, 문자열의 i번째 인덱스를 기준으로 1 ~ (i - 1)번째까지 순회하며 팰린드롬을 확인합니다.
3. 팰린드롬 확인은 두 포인터(Two Pointer)를 사용하여 확인했습니다.
4. 만약 문자열의 j ~ i 까지의 문자열이 팰린드롬이라면, 기존에 계산했던 값과 새로이 계산된 값 중 최소값을 반환합니다. 이때, j ~ i 문자열이 팰린드롬일 경우, 분할된 개수는 `dp[j - 1] + 1`과 같습니다. `dp[j - 1]`은 j 번째 바로 이전까지의 분할 개수의 최솟값이고 `1`은 새로 만들어진 팰린드롬의 개수입니다. 
5. 위 과정을 문자열의 길이만큼 반복합니다. 

팰린드롬 확인

우선, 두 포인터를 사용하여 인덱스 L ~ R의 문자열이 팰린드롬인지 확인하는 메서드를 작성합니다. 

 static boolean isPalindrome(int L, int R) {
    L--; R--; // dp 배열의 인덱스가 문자열 인덱스보다 1 크기 때문에
    while (L <= R) {
        if (str.charAt(L) != str.charAt(R)) return false;
        L++;
        R--;
    }
    return true;
}

다이나믹 프로그래밍을 위한 `dp[]` 배열을 편의를 위해 1번 인덱스부터 시작하도록 설정했기 때문에, 넘어오는 두 가지의 포인터의 인덱스를 1씩 감소시켜 주어야 해당 문자열 인덱스에 올바르게 접근할 수 있습니다. 

DP를 이용한 분할 개수의 최솟값

이제 1차원 `dp[]` 배열을 이용해 문자열의 길이만큼 탐색하며 최솟값을 찾아봅시다.

dp[1] = 1; // 1번 째는 팰린드롬 최대 1개
for (int i = 2; i < str.length() + 1; i++) {
    for (int j = 1; j < i; j++) {
        // j~i가 팰린드롬인지 확인
        if (isPalindrome(j, i)) {
            // 아직 체크한 이력이 없을 경우, 맨 뒤에 분할의 개수 추가
            if (dp[i] == 0) {
                dp[i] = dp[i - 1] + 1;
            }
            // 기존 계산값과 새로운 계산값 비교
            dp[i] = Math.min(dp[i], dp[j - 1] + 1);
        }
    }
    // 팰린드롬이 만들어지지 않았을 경우, 1개 추가
    if (dp[i] == 0) {
        dp[i] = dp[i - 1] + 1;
    }
}

`dp[1]` 즉, 문자열의 맨 첫 글자만 있는 경우는 팰린드롬이 1개만 존재하기 때문에, 1로 고정시켜 줍니다. 그 후, 2번 인덱스부터 탐색을 시작합니다.

여기서 i는 두 포인터의 R(맨 오른쪽), j는 두 포인터의 L(맨 왼쪽)을 의미합니다. 따라서, i를 고정해 놓은 채로 j를 i - 1까지 순회하며 `dp[]` 배열을 갱신해 줍니다.

만약, i ~ j 문자열이 팰린드롬일 경우, 기존에 갱신했던 `dp[i]`와 현재 계산된 분할 개수인 `dp[j - 1] + 1` 중 작은 값으로 `dp[i]`를 갱신합니다. 이때, `dp[i] == 0`인 경우는 한 번도 갱신된 적이 없는 상태이기 때문에, 나올 수 있는 최대값(분할 개수를 1개 추가하는 것)을 넣어줍니다. 

만약 j를 모두 순회했음에도 팰린드롬이 나오지 않았다면 `dp[i]`가 0 값을 가지고 있기 때문에, 분할 개수를 1개 추가하면 됩니다. 

 

위 과정을 통해 전체 문자열의 팰린드롬 분할 개수의 최솟값을 구할 수 있습니다. 

전체 코드

전체적인 코드는 다음과 같습니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Q1509 {
    static String str;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        str = br.readLine();
        int[] dp = new int[str.length() + 1]; // i 번 째까지의 분할 개수의 최소값

        dp[1] = 1; // 1번 째는 팰린드롬 최대 1개
        for (int i = 2; i < str.length() + 1; i++) {
            for (int j = 1; j < i; j++) {
                // j~i가 팰린드롬인지 확인
                if (isPalindrome(j, i)) {
                    // 아직 체크한 이력이 없을 경우, 맨 뒤에 분할의 개수 추가
                    if (dp[i] == 0) {
                        dp[i] = dp[i - 1] + 1;
                    }
                    // 기존 계산값과 새로운 계산값 비교
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
            // 팰린드롬이 만들어지지 않았을 경우, 1개 추가
            if (dp[i] == 0) {
                dp[i] = dp[i - 1] + 1;
            }
        }

        System.out.println(dp[str.length()]);
    }

    static boolean isPalindrome(int L, int R) {
        L--; R--; // dp 배열의 인덱스가 문자열 인덱스보다 1 크기 때문에
        while (L <= R) {
            if (str.charAt(L) != str.charAt(R)) return false;
            L++;
            R--;
        }
        return true;
    }
}