[BOJ 1509] 펠린드롬 분할 (Java, DP, Two pointer)
문제 링크
https://www.acmicpc.net/problem/1509
1509번: 팰린드롬 분할
세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하
www.acmicpc.net
문제 풀이
스스로 풀지 못하여서 기술 블로그를 참고 하였고, 이번 문제를 통해 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();
}
}