알고리즘/알문풀(백준, 프로그래머스, 코드트리)
[알고리즘] BOJ 10942 팰린드롬? (JAVA)
ragabys
2024. 3. 7. 01:30
https://www.acmicpc.net/problem/10942
10942번: 팰린드롬?
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
www.acmicpc.net
팰린드롬 유형 중 하나로, 백준이나 SW Expert 등에서도 몇 번 풀어본 적 있는 문제의 유형이었다.
하지만 N과 M 값이 크기 때문에, 일일히 매번 비교하면 시간초과가 무조건 날 수 밖에 없어
미리 모든 구간별로 팰린드롬 여부를 구해두고 사용할 필요성을 느꼈고,
모든 구간별로 구하기 위해 dp를 활용했다.
dp[i][j]는 i번재에서 j번째까지의 결과를 boolean 값으로 저장하고, num값과 dp값을 확인하여 그 값을
다음 dp에 저장하는 식으로 구현했다.
import java.io.*;
import java.util.*;
public class boj10942 {
static int N, M;
static int num[];
static boolean dp[][];
static StringBuilder sb;
public static void pre() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
sb = new StringBuilder();
num = new int[N + 1];
dp = new boolean[N + 1][N + 1]
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
num[i] = Integer.parseInt(st.nextToken());
dp[i][i] = true;
}
for (int i = 1; i < N; i++) {
if (num[i] == num[i + 1]) {
dp[i][i + 1] = true;
}
}
for (int i = 2; i < N; i++) {
for (int j = 1; j <= N - i; j++) {
if (num[j] == num[j + i] && dp[j + 1][j + i - 1]) {
dp[j][j + i] = true;
}
}
}
M = Integer.parseInt(br.readLine());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
if (dp[s][e]) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
}
}
public static void main(String args[]) throws IOException {
pre();
System.out.print(sb);
}
}
해당 코드의 실행 시간은 다음과 같다.
