백준 10942번 : 팰린드롬? [자바]

 

 

 

🧫 문제 분석

✔️ 출처

팰린드롬? 골드 4

 

📖 문제

팰린드롬 문제인데 주어지는 S, E 구간이 100만개다.

수열의 크기 N이 2000까지고  1<= S <= E <= N 이므로 

최악의 경우 O(NM) 이되어 20억가지수를 계산해야한다. 

 

그런데 투포인터로 하면 통과한다. 

 

그리고 다른사람들의 알고리즘 시간을 보니 500~700ms 대를 보았다.

 

참 좋은 공부가 된 것 같다. S, E 구간을 이중 배열로 구별하여 DP로 

이전의 구했던 구간을 다시 사용하여 현재 S,E 구간을 구하는 방식이다.

 

내가 이해한 바로는

1. 팰린드롬 길이가 1일 때 :  자기 자신이므로 항상 팰린드롬이다. 따라서 dp[i][i] = true이다. 

 

2. 팰린드롬 길이가 2일 때 : i, i+1이 같으면 팰린드롬이다. 따라서 seq[i] == seq[i+1] 이면 dp[i][i+1] = true이다.

 

3. 팰린드롬 길이가 3이상일때부터는 

시작지점(start)이 1부터 시작하여, 시작지점 + 팰린드롬 길이 (end)까지 구한다. 

우리가 알 수 있는 것은 start과 end 의 값이 같은지, 그리고 이전에 구한 start + 1 , end - 1 이 팰린드롬인지 확인할 수 있다.

start + 1, end - 1이 팰린드롬이라면 현재 start, end 값이 같으면 이 구간은 팰린드롬이므로 dp[start][end] = true이다.

 

좋은 학습이 되었다. 

---

🔅 문제 풀이 [투 포인터]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] seq = new int[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {

            st = new StringTokenizer(br.readLine());

            // 투 포인터로 s, e 지점에서 안쪽으로 모이는 형태로 비교한다.
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            boolean flag = false;

            do {
                if (seq[start] != seq[end]) {
                    flag = true;
                    break;
                }

                start++;
                end--;
            } while (start <= end);

            if (flag) {
                sb.append("0");
            } else {
                sb.append("1");
            }
            sb.append("\n");
        }


        System.out.print(sb.toString());
    }

}

 

 

🔅 문제 풀이 [DP]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] seq = new int[n + 1];
        boolean[][] dp = new boolean[n + 1][n + 1]; // [s][e] 로 나눔

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        // 길이가 1인 즉 1,1 2,2 3,3 구간의 수열은 항상 펠린드롬
        for (int i = 1; i <= n; i++) {
            dp[i][i] = true;
        }

        // 길이가 2인 즉,  1,2  2,3  3,4 구간의 수열은 두 수가 같으면 펠린드롬
        for (int i = 1; i < n; i++) {
            if (seq[i] == seq[i + 1]) {
                dp[i][i+1] = true;
            }
        }

        // 펠린드롬 길이
        for (int len = 2; len <= n; len++) {
            // 시작 위치, 전체 길이에서 팰린드롬 길이를 뺀 만큼만
            for (int start = 1; start <= n - len; start++) {

                // start + 1, end - 1 이 팰린드롬이고, start,end가 같다면 팰린드롬
                if (dp[start + 1][start + len - 1] && seq[start] == seq[start + len]) {
                    dp[start][start + len] = true;
                }
            }
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            // 투 포인터로 s, e 지점에서 안쪽으로 모이는 형태로 비교한다.
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            if (dp[start][end]) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }


        System.out.print(sb.toString());
    }

}

 

❗ 오답노트 / 필요한 지식