BOJ 10942
위 문제는 백준 사이트의 알고리즘 10942문제에 관한 설명입니다.
문자열 처리 연습용 문제입니다.
팰린드롬?
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 N개를 칠판에 적는다.
그 다음, 명우에게 질문을 총 M번 한다.
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며,
S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며,
명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
- S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
- S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
- S = 3, E = 3인 경우 1은 팰린드롬이다.
- S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.
출력
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
소스코드
package day0916;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int[] number;
static boolean[][] palin;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
number = new int[N + 1];
palin = new boolean[N + 1][N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
number[i] = Integer.parseInt(st.nextToken());
}
isPalindrom();
M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int t1 = Integer.parseInt(st.nextToken());
int t2 = Integer.parseInt(st.nextToken());
if(palin[t1][t2])sb.append("1\n");
else sb.append("0\n");
}
System.out.println(sb);
}
public static void isPalindrom(){
for(int i = 1; i <= N; i++)
palin[i][i] = true;
for(int i = 1; i <= N - 1; i++)
if(number[i] == number[i + 1]) palin[i][i + 1]= true;
for(int i = 2; i < N; i++){
for(int j = 1; j <= N - i; j++){
if(number[j] == number[j + i] && palin[j + 1][j + i - 1])
palin[j][j + i] = true;
}
}
}
}
해당 문제는 DP, 문자열 처리를 하는 문제였습니다.
이번문제에선 시간초과를 잡는게 제일 문제였습니다.
처음엔 Scanner를 사용해서 하다가 제한 시간이 0.5초라고 되어있기에,
bufferedReader와 StringBuilder를 사용해서 입력 출력을 했습니다.
팰린드롬이란 ?
앞뒤가 똑같은 단어
즉, 앞 뒤가 좌우대칭으로 같은 단어를 말하는데
예를 들어 봅시다.
- 한 자릿수 : 1 = 1 이므로 팰린드롬입니다.
- 두 자릿수 : 12 /= 21 이므로 팰린드롬이 아닙니다.
만약 두 자릿수가 팰린드롬이기 위해서는, 자릿수에 같은 숫자가 들어가야합니다. - 세 자릿수 : 121 = 121 (팰린드롬), 123 /= 321 (팰린드롬이 아님)
- 네 자릿수 : 1221 = 1221 (팰린드롬), 1231 /= 1321 (팰린드롬이 아님)
이렇게 구별해 놓고 보았을 때 팰린드롬이 성립하기 위해서는 아래와 같은 조건으로 크게 구분합니다.
1) 양 끝의 두 문자가 같다. 2) 양 끝의 두 문자를 제외하고 안에 있는 단어가 팰린드롬이다.
순차적으로 코드를 따라가 봅시다.
값을 입력하는 부는 간단하니 넘어가겠습니다.
public static void isPalindrom(){
for(int i = 1; i <= N; i++)
palin[i][i] = true;
for(int i = 1; i <= N - 1; i++)
if(number[i] == number[i + 1]) palin[i][i + 1]= true;
for(int i = 2; i < N; i++){
for(int j = 1; j <= N - i; j++){
if(number[j] == number[j + i] && palin[j + 1][j + i - 1])
palin[j][j + i] = true;
}
}
}
함수 내부를 봅시다.
처음에 isPalindrom()을 시작하게 되면 전부 true로 초기화를 합니다.
(길이가 1인것 전부 팰린드롬으로.)
그리고 다음 분기문에선 1부터 시작해서 i가 N-1까지 반복을 하는데
길이가 2일 때(즉, 두 개의 수만 선택했을 때)이므로 두 수가같다면 팰린드롬.
마지막 분기문은 길이가 3이상일 경우입니다.
양끝은 되었으니 시작은 2부터 시작을 합니다.
그리고 j를 활용해서 원하는 길이만큼의 팰린드롬을 확인합니다.
돌아와서
if(palin[t1][t2])sb.append("1\n");
else sb.append("0\n");
조건을 보고 t1 = 시작점, t2 = 끝점을 확인해 봤을 때의 팰린드롬인지 확인한 값을
sb에 담고 출력 시켜줍시다.