[BOJ 1509] 펠린드롬 분할 (Java, DP, Two pointer)

 

 

---

문제 링크

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

1509번: 팰린드롬 분할

---

문제 풀이 

스스로 풀지 못하여서 기술 블로그를 참고 하였고, 이번 문제를 통해 DP 기법과 Two Poiner 기법 응용하는 방식에 대해 처음으로 알게 되었다. 풀이 후 몇일 있다가 손으로 그려보고 Top-Down, Bottom-Up 풀이하는데 역시나 쉽지 않은 문제인 것 같다. 가짜문제 정의, 초기화 항목 .. 단순히 DP배열 하나만으로 풀이가 어려운 문제 또한 당연히 나올 것이기 때문에 좋은 연습이 된 문제였다.

 

- DP, Two Pointer 응용 문제 

- 처음 입력 받은 텍스트를 int 형으로 변환하여 배열 초기화 수행

- boolean[][] palindrome 채우는데 시간 복잡도 O(N^2)

- Bottom-Up 방식 풀이시 O(N^2) 

- Top-Down 풀이시 O(2500!), 재귀로 풀이시 return 조건문과 memorization기법을 사용하여 시간내 풀이 가능

 

*팰린드롬(대칭성을 이루는 텍스트, 숫자)의 경우 아래와 같은 특징을 가진다.

- len = 1일때 자기자신은 팰린드롬 o

- len = 2일때 i 와 i + 1번째 텍스트(숫자)가 동일한 경우 팰린드롬 o

- len = 3이상의 경우 시작과 끝이 동일하고, (시작과 끝을 제외한) 나머지 범위도 팰린드롬인 경우 팰린드롬 o 

예) i = 1, j = 3일 때 (A[1] == A[3] && isPalindrom(2, 2)) 조건이 True이면 (1,3)은 팰린드롬 o

 

 

* 입력 예시 4 의 경우

QWERTYTREWQWERT

{QWERTYTERWQ, W, E, R, T} 로 분할의 개수 5(최소값) 구할 수 있다

 

 

Bottom-Up 방식 풀이 시

- DP[0] = 0 초기화

예로 i = 11일 때 j는 1 ~ 11 까지 루프문 조회 (투 포인터 방식)

palindrome[j][i] == true 인 경우 DP[11] = Math.min(DP[11], DP[j - 1] + 1)을 하여 최소값을 갱신해 간다. 이때 결과 DP 배열은 아래와 같이 채워진다. 

 

(1, 11) 경우 QWERTYTERWQ로 DP[0] + 1 하여 1이 되게 되고 (11,11)의 경우 자기자신(팰린드롬) 이기 때문에 DP[10] + 1이나 최소값이 아니기 때문에 갱신되지 않음 

 

 

Top-Down 방식 풀이시

- 재귀 함수를 호출하는 하향식의 경우 리턴 조건문과 메모리제이션에 주의 해야 한다.

- rec(15) (예제의 입력 length = 15) 호출하게 되면 작은 문제부터 풀이하여 최종적으로 큰 문제를 풀게 된다

- 마찬가지로 palindrome 여부를 활용하여 구하면 된다 

 

static void rec(int i) {
    if(i < 1) return 0; 
    if(DP[i] != Integer.MAX_VALUE) return DP[i]; // memorization

    int value = Integer.MAX_VALUE;
    for(int j = 1; j <= i; j++) {
       value = Math.min(value, rec(j - 1) + 1);
    }
    
    return DP[i] = value;
}

 

{QWERTYTERWQ, W, E, R, T} 조합에 대해  

 

rec(15) 호출 시 

- (7, 15) 팰린드롬이므로 rec(6) 호출 

- (15, 15) 팰린드롬이므로 rec(14) 호출

 

rec(14) 호출시 

- (8, 14)  팰린드롬이므로 rec(7) 호출

- (14, 14) 팰린드롬이므로 rec(13) 호출

 

...

 

rec(11) 호출시

- (1, 11) 팰린드롬이므로 rec(0) 호출   -- 여기서부터 1 이므로, 다시 올라가서 DP[15] 값이 누적됨

- (11, 11) 팰린드롬이므로  rec(10) 호출

 

Bottom-Up과 마찬가지로 11번째까지만 내려가더라도 DP[0] + 1 = 1 이기 때문에 5라는 최소값을 구할 수 있음

---

제출 코드 

(1) Bottom-Up 방식

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static Character[] TEXT;
    static boolean[][] PALINDROME;

    public static void main(String[] args) throws IOException {
        input();

        preprocess();
        bottomUp();

        output();
    }


    private static void input() {
        String input = inputProcessor.nextLine();

        int len = input.length();
        TEXT = new Character[len + 1];

        for(int i = 1; i <= len; i++) {
            TEXT[i] = input.charAt(i - 1);
        }

        PALINDROME = new boolean[len + 1][len + 1];
    }

    private static void preprocess() {
        int len = TEXT.length - 1;
        for(int i = 1; i <= len; i++) {
            PALINDROME[i][i] = true;
        }

        for(int i = 1; i < len; i++) {
            if(TEXT[i] == TEXT[i + 1]) {
                PALINDROME[i][i + 1] = true;
            }
        }

        for(int l = 3; l <= len; l++) {
            for(int i = 1; i <= len - l + 1; i++) {
                int j = i + l - 1;
                if(TEXT[i] == TEXT[j] && PALINDROME[i + 1][j - 1]) {
                    PALINDROME[i][j] = true;
                }
            }
        }
    }

    private static void bottomUp() {
        int[] dp = new int[TEXT.length];
        dp[0] = 0;
        dp[1] = 1;

        for(int i = 2; i <= TEXT.length - 1; i ++) {
            dp[i] = Integer.MAX_VALUE;

            for(int j = 1; j <= i; j++) {
                if(PALINDROME[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        sb.append(dp[TEXT.length - 1]);
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}

 

(2) Top-Down 방식

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

public class Main {
    
    static String input;
    static int TEXT_LENGTH;

    static int[] alphabet, DP;
    static boolean[][] PALINDROME;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        input = br.readLine();
        TEXT_LENGTH = input.length();

        alphabet = new int[TEXT_LENGTH + 1];
        for(int i = 1; i <= TEXT_LENGTH; i++) {
            alphabet[i] = input.charAt(i - 1) - 'A';
        }
    }

    static void fulfillPalindrome() {
        PALINDROME = new boolean[TEXT_LENGTH + 1][TEXT_LENGTH + 1];

        for(int i = 1; i <= TEXT_LENGTH; i++) {
            PALINDROME[i][i] = true;
        }

        for(int i = 1; i < TEXT_LENGTH; i++) {
            if(alphabet[i] == alphabet[i + 1]) PALINDROME[i][i + 1] = true;
        }

        for(int len = 3; len <= TEXT_LENGTH; len++) {
            for(int i = 1; i <= (TEXT_LENGTH - len + 1); i++) {
                int j = i - 1 + len;
                if(alphabet[i] == alphabet[j] && PALINDROME[i + 1][j - 1]) {
                    PALINDROME[i][j] = true;
                }
            }
        }
    }

    static void pro() {
        DP = new int[TEXT_LENGTH + 1];

        Arrays.fill(DP, Integer.MAX_VALUE);
        DP[0] = 0;

        System.out.println(rec(TEXT_LENGTH));
    }

    static int rec(int j) { // top-down 방식
        if(j < 0) return 0;
        if(DP[j] != Integer.MAX_VALUE) return DP[j];

        int value = Integer.MAX_VALUE;
        for(int i = 1; i <= j; i++) {
            if(PALINDROME[i][j]) {
                value = Math.min(value, rec(i - 1) + 1);
            }
        }

        return DP[j] = value;
    }

    public static void main(String[] args) throws Exception {
        input();

        fulfillPalindrome();

        pro();
    }
    
}