팰린드롬?

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

풀이

팰린드롬이란 문자열을 뒤집었을 떄 원본 문자열과 동일한 문자열을 의미한다.

이전의 포스팅에서 문자열 뒤집기 알고리즘을 비교한 적이 있었는데 api등에서 구현된 방법을 보면 n/2인 방법을 사용하고 있기때문에 팰린드롬 판단하는데 드는 시간은 n/2라고 생각하면 된다.

하지만 이 문제 같은 경우 m개의 입력값에 대해 하나하나 팰린드롬인지 검사하여 결과값을 구하면 중복되게 팰린드롬 검사를 하는 경우가 있어 시간이 초과하게 된다.

따라서 팰린드롬을 검사하는 과정에서 그 보다 작은 팰린드롬의 검사결과를 저장해야 한다.

1 2 3 2 1에서 "1 5"는 팰린드롬이다. 이때 "2 4" 또한 팰린드롬이고 "1 5"가 팰린드롬인지 검사하는 과정에서 "2 4"가 팰린드롬인지 검사하는 과정이 있다.

따라서 이 결과값들을 미리 dp 테이블에 저장하고 나중에 불러오는 식으로 구현한다.

구현할 때 미리 dp 테이블을 -1로 초기화하여 갱신이 끝난 곳은 검사하지 않도록 하여 탐색시간을 줄이고 또 s <= e 이기 때문에 j <= i일 경우도 검사하지 않는다.

또한 팰린드롬 검사는 재귀를 통해 구현하면 쉽게 풀린다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int Answer;
    static int n, m;
    static int[] p;
    static ArrayList<String> ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        String[] line = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(line[i - 1]);
        }

        int[][] dp = new int[n + 1][n + 1];

        for(int i = 0;i<=n;i++)
            Arrays.fill(dp[i], -1);

        for(int i = 1;i<=n;i++)
            dp[i][i] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= i; j--) {
                if(j <= i)
                    continue;
                if(dp[i][j] != -1)
                    continue;
                init(dp, arr, i, j);
            }
        }

        m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int dest = Integer.parseInt(input[1]);
            if (dp[start][dest] == 1)
                bw.write("1\n");
            else
                bw.write("0\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static int init(int[][] dp, int[] arr, int x, int y) {
        if((x + y) % 2 == 0) {
            if (arr[x] == arr[y]) {
                if (x == y) {
                    return dp[x][y] = 1;
                }
            int a = init(dp, arr, x + 1, y - 1);
            dp[x][y] = a;
            dp[y][x] = a;
                return dp[x][y];
            } else {
                return 0;
            }
        }
        else {
            if (arr[x] == arr[y]) {
                if (x == y + 1) {
                    dp[x][y] = 1;
                    dp[y][x] = 1;
                    return 1;
                }
                int a = init(dp, arr, x + 1, y - 1);
                dp[x][y] = a;
                dp[y][x] = a;
                return dp[x][y];
            } else {
                dp[x][y] = 0;
                dp[y][x] = 0;
                return 0;
            }
        }
    }
}