10942번 - 팰린드롬?
문제 풀이 시간 : 1시간
문제 요약
- 홍준이가 자연수 N개를 칠판에 적는다.
- 명우에게 질문을 총 M번 한다.
- 질문은 두 정수 S, E (1 ≤ S ≤ E ≤ N)로 나타낸다.
- S번째 수부터 E번째 수까지 팰린드롬을 이루는지 확인한다.
문제 풀이
처음에는 그냥 무작정 주어지는 수를 배열에 저장하고
S 와 E가 주어질때마다 앞뒤로 비교하며 다른게 나오면 팰린드롬이 아닌 것이니까 바로 false를 출력하고, S와 E가 같아질때까지 모두 같다면 팰린드롬인 것으로 구현을 했다.
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> arr = new ArrayList<>(N + 1);
arr.add(-1);
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
arr.add(Integer.parseInt(st.nextToken()));
}
int 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());
boolean pelin = true;
while(s<=e){
if(!Objects.equals(arr.get(s), arr.get(e))){
pelin = false;
break;
}
s++;
e--;
}
int result = pelin ? 1:0;
sb.append(result).append("\n");
}
System.out.println(sb);
}
}
이 코드의 문제는 N은 최대 100,000이 될 수 있고, M은 최대 1,000,000이 될 수 있다는 것이다.
즉, 최악의 경우 100,000,000,000 이 되는 것이다.
그러니까 당연히 시간초과가 날 수밖에 없는 것이다.
그렇다면 이 문제는 어떤식으로 풀어야 할까?
바로바로 DP이다.
설명을 듣는 것보다 직접 코드를 보는게 빠를 것이라고 생각한다.
바로 코드를 보자.
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static boolean[][] dp;
public static ArrayList<Integer> arr;
public static boolean find(int s, int e) {
if(s>e){ //S가 E를 넘었다는 것은 S와 E의 차가 홀수라는 뜻. 또한, 이전까지 문제가 없었다는 것이므로 팰린드롬.
return true;
}
if(dp[s][e]){ //이미 해당 값이 구해져 있다면 바로 리턴
return dp[s][e];
}
if (s == e) { //S와 E의 차가 짝수였고, 모두 값이 같았음
dp[s][e] = true;
return true;
}
if (!arr.get(s).equals(arr.get(e))) { //S와 E의 값이 다르면 팰린드롬 아님.
dp[s][e] = false;
return false;
}
dp[s][e] = find(s + 1, e - 1); //다음 칸 비교
return dp[s][e];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new ArrayList<>(N + 1);
dp = new boolean[N + 1][N + 1];
arr.add(-1);
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
arr.add(Integer.parseInt(st.nextToken()));
}
int 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());
int result = find(s, e) ? 1 : 0;
sb.append(result).append("\n");
}
System.out.println(sb);
}
}
함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.