10942번 - 팰린드롬?

2024-08-06

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
홍준이가 자연수 N개를 칠판에 적는다.

•
명우에게 질문을 총 M번 한다.

•
질문은 두 정수 S, E (1 ≤ S ≤ E ≤ N)로 나타낸다.

•
S번째 수부터 E번째 수까지 팰린드롬을 이루는지 확인한다.

문제 풀이

처음에는 그냥 무작정 주어지는 수를 배열에 저장하고

S 와 E가 주어질때마다 앞뒤로 비교하며 다른게 나오면 팰린드롬이 아닌 것이니까 바로 false를 출력하고, S와 E가 같아질때까지 모두 같다면 팰린드롬인 것으로 구현을 했다.

초기 코드

Java

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이다.

설명을 듣는 것보다 직접 코드를 보는게 빠를 것이라고 생각한다.

바로 코드를 보자.

최종 코드

Java

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);
    }
}