BOJ#10942 팰린드롬?

BOJ#10942 팰린드롬?

* 문제

https://www.acmicpc.net/problem/10942

* 풀이

문자열 중에서 팰린드롬에 대하여 지금 공부할지 아니면 나중에 공부할지 고민했습니다만..

(알고리즘 대회가 아니면 별로 쓸 일이 없기 때문에)

간단히 O(N^2) 풀이와 O(N)풀이에 대해 공부해 보았습니다.

완벽히 이해한 상태가 아니기 때문에 설명은 나중에 추가하도록 하겠습니다.

팰린드롬은 너무 어렵습니다..

팰린드롬 공부 링크 : http://stack07142.tistory.com/128

---

* 나의 코드

O(N), Manacher's Algorithm

- 어느 한 원소를 기준으로 좌/우로 넓혀가면서 검사 -> N이 홀수인 경우에는 문제없지만, N이 짝수인 경우에는 문제가 생김 -> 일괄적으로 2*N -1 처리

- R : p를 중심으로 한 팰린드롬의 맨 오른쪽 위치

- 검사하는 항목이 R의 범위 안에 있으면, 팰린드롬의 성질에 따라 불필요한 검사는 생략할 수 있다는 것(이미 앞에서 검사했으므로)

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static final int YES = 1;
    static final int NO = 0;

    static int[] S = new int[2000000];
    static int[] A = new int[2000000];

    public static void main(String[] args) throws IOException {

        int N; // 수열의 크기
        int M; // 질문의 개수

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        N = 2 * N - 1;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i += 2) {

            S[i] = Integer.parseInt(st.nextToken());
        }

        // solve
        manacher(N);

        M = Integer.parseInt(br.readLine());

        int left, right, center, radius;
        for (int i = 0; i < M; i++) {

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

            left = (Integer.parseInt(st.nextToken()) - 1) * 2;
            right = (Integer.parseInt(st.nextToken()) - 1) * 2;

            center = (left + right) / 2;
            radius = (right - left) / 2;

            bw.write(A[center] >= radius ? YES + "\n" : NO + "\n");
        }

        bw.flush();

        bw.close();
        br.close();

    }

    static void manacher(int N) {

        int R = -1;
        int p = -1;

        for (int i = 0; i < N; i++) {

            // 1. A[i]의 초기값 설정

            // R범위에 i가 포함되지 않는 경우
            if (R < i) {

                A[i] = 0;
            }
            // R범위에 i가 포함되는 경우, 팰린드롬의 정의에 따라 불필요한 검사를 하지 않는다
            else {

                A[i] = Math.min(R - i, A[2 * p - i]);
            }

            // 2. i를 기준으로 양옆으로 범위를 넓혀가면서 검사
            while (((i - A[i] - 1) >= 0 && (i + A[i] + 1) < N)
                    && (S[i - A[i] - 1] == S[i + A[i] + 1])) {

                A[i]++;
            }

            // 3. R과 p를 갱신
            if (i + A[i] > R) {

                R = i + A[i];
                p = i;
            }
        }
    } // ~ Manacher
}

O(N^2) 풀이 - 1

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

/**
 * BOJ#10942 팰린드롬?
 * https://www.acmicpc.net/problem/10942
 */

public class Main3 {

    static final int YES = 1;
    static final int NO = 0;

    static int[] A = new int[2001];
    static int[][] dp = new int[2001][2001];

    public static void main(String[] args) throws IOException {

        int N; // 수열의 크기
        int M; // 질문의 개수

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {

            A[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());

        // solve
        for (int i = N; i > 0; i--) {

            for (int j = i; j < N + 1; j++) {

                if (i == j) {

                    dp[i][j] = YES;
                } else if (i == j - 1 && A[i] == A[j]) {

                    dp[i][j] = YES;
                } else if (dp[i + 1][j - 1] == YES && A[i] == A[j]) {

                    dp[i][j] = YES;
                } else {

                    dp[i][j] = NO;
                }
            }
        }

        for (int i = 0; i < M; i++) {

            int S, E;

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

            S = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            System.out.println(dp[S][E]);
        }
    }
}

O(N^2) 풀이 - 2

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

/**
 * BOJ#10942 팰린드롬?
 * https://www.acmicpc.net/problem/10942
 */

// 22328 KB    2984 MS

public class Main2 {

    static final int YES = 1;
    static final int NO = 0;

    static int[] A = new int[2001];
    static int[][] dp = new int[2001][2001];

    public static void main(String[] args) throws IOException {

        int N; // 수열의 크기
        int M; // 질문의 개수

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {

            A[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());

        // solve
        for (int i = 0; i < M; i++) {

            int S, E;

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

            S = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            System.out.println(solve(S, E));
        }
    }

    static int solve(int S, int E) {

        // memoization
        if (dp[S][E] > 0) {

            return dp[S][E];
        }

        // solve
        if (S == E) {

            return YES;
        }

        int ret = NO;
        if (S + 1 == E) {

            if (A[S] == A[E]) {

                return dp[S][E] = YES;
            }
        } else {

            if (A[S] == A[E]) {

                ret = solve(S + 1, E - 1);
            }
        }

        return dp[S][E] = ret;
    }
}