[백준] 10942번. 팰린드롬?(JAVA)
문제
https://www.acmicpc.net/problem/10942
풀이
import java.io.*;
import java.util.*;
public class Main{
static int n, m;
static int[] arr;
static int[][] answer;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
arr = new int[n+1];
for(int i = 1; i < n+1; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
answer = new int[n+1][n+1];
// 길이 1인 경우는 무조건 팰린드롬
for(int i = 1; i <= n; i++){
answer[i][i] = 1;
}
// 길이 2인 경우 처리
for(int i = 1; i < n; i++){
if(arr[i] == arr[i+1]){
answer[i][i+1] = 1;
}
}
// 길이가 3 이상인 경우 처리
for(int length = 2; length < n; length++){ // 구간 길이
for(int j = 1; j <= n - length; j++){ // 시작점 j
int k = j + length; // 끝점 k
if(arr[j] == arr[k] && answer[j+1][k-1] == 1){
answer[j][k] = 1;
}
}
}
// 쿼리 처리
m = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i = 0; i < m; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
sb.append(answer[x][y]).append("\n");
}
System.out.print(sb.toString());
}
}
팰린드롬을 처리하기 위해서 가장 쉬운 방법은 시작과 끝에서부터 줄여오며 비교를 하는 방법이 있다. 다만 모든 인덱스에 대한 검사를 실행해야 하고 이는 시간초과가 발생할 수도 있다.
이를 해결하기 위해 dp라는 방식을 떠올려보았다.
팰린드롬을 효율적으로 처리하기 위한 방식은 뭐가 있을까? 라는 고민과 함께 만들어가는 방법을 생각했다.(dp의 경우 점화식을 세워야하기 때문에 항상 어떻게 만드는지를 정확하게 이해하는 것이 중요하다. 이 과정에서 이 전의 값을 이용하는 방법에 대해서만 꾸준히 고려하며 진행하자.)
1. 길이가 1인 경우는 무조건 팰린드롬이 된다.
2. 길이가 2인 경우는 앞의 값과만 비교하면 된다. 이때 dp나 다른 값을 가져와서 사용할 수 있는 방법이 있을까? 없는 것 같다.
3. 길이가 3 이상인 경우엔 시작과 끝만을 비교하고, 시작과 끝을 제외하고의 시작과 끝에 대한 값이 팰린드롬인지 보면 된다.
EX) 1 2 3 2 1 인 경우를 생각해보자.
각각의 1의 길이는 모두 팰린드롬이 된다.
| 1 | 2 | 3 | 2 | 1 | |
| 1 | T | T | T | T | T |
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 |
열이 각 인덱스의 값이 되고, 행은 길이가 된다. 그럼 1행을 모두 T로 채워주자.
2열을 채워보자.
| 1 | 2 | 3 | 2 | 1 | |
| 1 | T | T | T | T | T |
| 2 | F | F | F | F | |
| 3 | |||||
| 4 | |||||
| 5 |
1의 경우 2와, 2의 경우 3과 비교하는 식으로 진행하면 되므로 모두 F로 채우면 된다.
이제 중요한 3열을 채워보자.
| 1 | 2 | 3 | 2 | 1 | |
| 1 | T | T | T | T | T |
| 2 | F | F | F | F | |
| 3 | F | T | F | ||
| 4 | |||||
| 5 |
1열부터 채워가는 방식을 이해해보자. 1, 2, 3이기 때문에 팰린드롬이 아니다. 이를 이해해보면 1과 3을 비교한다. 이 때 F가 나오기 때문에 절대 팰린드롬이 될 수 없다.
2열을 채워보자. 일단 2열과 4열을 비교하면 2 == 2로 트루가 된다. 그럼 중간에 3을 생각하면 되는데 3열의 값이 T이기때문에 문제가 없다.
마지막으로 1 2 3 2 1인 경우를 생각해보자.
시작과 끝이 같다. 그럼 중간인 2 3 2인 경우 2에서 길이가 3인게 이미 체크되어있고 T인 것을 알고있다.
이것을 코드로 옮기면 된다!
기본값인 1,2에 대해 처리해주고 나머지에 대한 dp 코드를 작성해주면 된다!