[백준 1509] - 팰린드롬 분할(JAVA)[골드1]

문제

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

1509번: 팰린드롬 분할

 

문제 풀이

팰린드롬 시리즈는 유명한 문제이다.

팰린드롬에 대해서 간단하게 설명하자면 가운데를 기준으로 일치하는  문자열을 의미한다.

예를 들어서 

ABA라는 문자열이 팰린드롬에 해당한다. 그 외에도 문자열의 길이가 1인 문자열도 팰린드롬에 해당한다.

해당 문제를 풀기 전에 팰린드롬에 개념을 알고 문제를 진행하면 풀기 수월하다.

 

우리는 문자열에서 팰린드롬의 집합들을 계산해야 한다.

나는 재귀호출로 팰린드롬을 모두 계산했고, 2차원 배열을 사용했다.

palindrom [start][end] = 문자열의 start~ end 부분이 팰린드롬인지에 대한 여부를 뜻한다.

 

기본적인 흐름은 재귀를 통해서 팰린드롬의 여부를 판단한다.

모든 문자열에 대해서 start와 end를 계산하기보단 메모이제이션을 이용해서 계산했던 부분은 계산하지 않고, 그 값을 이용한다.

(문자열의 길이가 길 경우 모든 경우의 수를 계산하는 과정은 시간초과를 발생할 수 있기 때문이다)

 

간단하게 얘기하고 가자면 ABCBADABCBA라는 문자열이 있을 경우

우리는 1번(A) ~ 5번(A) , 7번(A) ~ 11번(A)까지 팰린드롬이라는 사실을 계산했다.

그렇다면 이 계산한 내용을 저장해서 1~11번을 계산할 때 앞서 계산했던 영역들을 이용해서 재귀의 깊이를 줄이는 것이다.

 

코드적으로는 다음과 같다.

public static int pal(int start, int end) {
    if (palindrom[start + 1][end + 1] != -1) { //이미 계산을 한 경우
        return palindrom[start + 1][end + 1];
    }

    if (pal.charAt(start) != pal.charAt(end)) {
        palindrom[start + 1][end + 1] = 0;
        return palindrom[start + 1][end + 1];
    } else { //같을 경우
        palindrom[start + 1][end + 1] = 1;
        if (start + 1 <= end - 1) { //다음 검사에서 교차하지 않는다면 계속해서 검사를 해서 누적해야함.
            palindrom[start + 1][end + 1] = palindrom[start + 1][end + 1] * pal(start + 1, end - 1);
        }
        return palindrom[start + 1][end + 1];
    }
}

2차원 배열인 palindrom은 계산의 여부를 판단하기 위해서 -1로 초기화를 했습니다.

값이 0이라면 팰린드롬이 아니라는 뜻이고, 1이라면 팰린드롬이라는 뜻입니다.

• 만약 값이 -1이면 값을 반환
• 비교하려는 두 위치의 글자가 다를 경우는 값을 0으로 변경하고, 값을 리턴합니다.
• 만약 글자가 같을 경우는 해당 구간은 팰린드롬이라는 가능성이 있습니다. 왜냐하면 그다음 구간도 판단을 해줘야 하기 때문입니다.
  • ABCA 같은 경우를 의미
• 다음 구간에 대한 판단의 여부는 start가 end를 넘어서지 않을 때입니다.
  • 넘어서지 않는다면 다음 구간의 결괏값에 따라 팰린드롬의 여부가 결정 납니다.
  • 저는 곱하기 연산을 통해서 1*1인경우는 팰린드롬, 1*0인 경우는 팰린드롬이 아니라고 계산했습니다.

 

이렇게 모든 팰린드롬을 계산했다면 다음은 팰린드롬을 분할해서 최소한의 덩어리로 팰린드롬을 구성할 수 있는 값을 찾아야 합니다.

 

dp[i] -> i번째 글자까지 최소한의 덩어리 수

점화식은 다음과 같습니다.

dp[e] = Math.min(dp[e], dp[s-1] +1)

코드를 통해서 확인해 보겠습니다.

public static void palDp() {
    for (int e = 1; e <= length; e++) { //end는 1부터 길이까지 돌리 기
        dp[e] = 2501;
        for (int s = 1; s <= e; s++) { //start는 1부터 e까지
            if (palindrom[s][e] == 1) { //팰린드롬이라는 뜻.
                dp[e] = Math.min(dp[e], dp[s - 1] + 1); //e까지의 최소 팰린드롬의 수는
            }
        }
    }
}

• e는 검사하려는 구간입니다. 
  • dp [1]은 1글자까지 팰린드롬의 최소 덩어리수
• 이렇게 끝지점을 정해주고 시작점을 1부터 e까지 돌려줍니다.
  • 만약 해당 구간이 팰린드롬이라면 연산을 합니다.
  • 이미 저장되어 있던 덩어리수와 그 앞부분의 결과인 dp[s-1]에 +1을 해줍니다.

예를 들어서 e가 6이고 s가 3일 때를 가정하면

3~6이 팰린드롬일 경우 우리는 1~2의 팰린드롬 최소 덩어리 수가 필요합니다. 해당 결괏값에 +1을 한 것이 dp[6]의 후보입니다.

다른 후보는 이미 구해져 있는 dp[6]이 될 것입니다.

이렇게 모든 dp 연산을 마무리하면 dp[length]에는 length까지의 최소 덩어리 수가 계산될 것입니다.

 

전체 코드

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static String pal;
    static int[][] palindrom;
    static int length;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        palDp();
        System.out.print(dp[length]);
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        pal = st.nextToken();
        length = pal.length();
        palindrom = new int[length + 1][length + 1];
        dp = new int[length + 1];
        for (int i = 0; i <= length; i++) {
            for (int j = 0; j <= length; j++) {
                palindrom[i][j] = -1;
            }
        }
    }

    // 팰린드롬 분할 집합의 개수.
    public static void solution() {
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                pal(i, j);
            }
        }
    }

    public static int pal(int start, int end) {
        if (palindrom[start + 1][end + 1] != -1) { //이미 계산을 한 경우
            return palindrom[start + 1][end + 1];
        }

        if (pal.charAt(start) != pal.charAt(end)) {
            palindrom[start + 1][end + 1] = 0;
            return palindrom[start + 1][end + 1];
        } else { //같을 경우
            palindrom[start + 1][end + 1] = 1;
            if (start + 1 <= end - 1) { //다음 검사에서 교차하지 않는다면 계속해서 검사를 해서 누적해야함.
                palindrom[start + 1][end + 1] = palindrom[start + 1][end + 1] * pal(start + 1, end - 1);
            }
            return palindrom[start + 1][end + 1];
        }
    }

    public static void palDp() {
        for (int e = 1; e <= length; e++) { //end는 1부터 길이까지 돌리 기
            dp[e] = 2501;
            for (int s = 1; s <= e; s++) { //start는 1부터 e까지
                if (palindrom[s][e] == 1) { //팰린드롬이라는 뜻.
                    dp[e] = Math.min(dp[e], dp[s - 1] + 1); //e까지의 최소 팰린드롬의 수는
                }
            }
        }
    }
}