[BOJ] 팰린드롬?

🎨 문제

10942번: 팰린드롬?

📘 풀이

이 문제는 DP로 풀 수 있습니다. 문제를 정리하면 다음과 같습니다.

1. 길이가 최대 2,000인 수열이 주어진다.
2. 수열의 [S, E] 구간의 수가 펠린드롬인지 판별한다.
3. 판별 질의는 최대 1,000,000 주어진다.

주어진 구간이 펠린드롬인지 판별하는 일반적인 방법은 구간 양 끝점부터 서로 같은 수인지 비교를 하는 방법입니다. 이 경우 한 쿼리 당 최대 수열의 길이만큼의 확인이 필요합니다. 하지만 질의가 1,000,000번 주어지기 때문에 매 번 비교를 할 수 없습니다. 그래서 이전 쿼리의 결과를 저장(메모이제이션)하고 검색 구간이 곂친다면 해당 결과를 사용하도록 코드를 작성했습니다.

 

검색 구간의 시점과 종점으로 DP 배열을 만들었습니다.

int[][] DP = new int[2001][2001];

탑다운 방식을 활용하여 구현을 하였습니다. 선언부는 다음과 같습니다. 시점과 종점을 인자로 해당 구간의 수열이 팰린드롬이면 1, 아니면 0을 리턴합니다.

int solve(int startInclusive, int endInclusive)

종료 조건(기저 사실)

• 검색 구간의 길이가 1인 경우 ➡️ 1
• 검색 구간의 길이가 2인 경우 ➡️ 양 끝점이 같으면 1, 아니면 0

if (startInclusive == endInclusive) return 1;
if (endInclusive - startInclusive == 1) {
    return ARRAY[startInclusive] == ARRAY[endInclusive] ? 1 : 0;
}

메모이제이션으로 이미 팰린드롬인 구간은 비교 없이 바로 리턴

DP[startInclusive][endInclusive]가 0인 경우 아직 비교해보지 않았거나 팰린드롬이 아닌 경우입니다. 전자인 경우 비교해보면 되지만 후자인 경우 한 번의 계산만으로도 팰린드롬이 아닌 것을 확인할 수 있기 때문에 DP 배열을 정답 후보가 아닌 값으로 초기화하지 않아도 큰 영향이 없을 것으로 보입니다.

if (DP[startInclusive][endInclusive] == 1) return DP[startInclusive][endInclusive];

인자로 주어진 시점과 종점을 비교하고 만약 같다면 solve(startInclusive + 1, endInclusive - 1)을 호출해 남은 구간도 비교해줍니다.

int result = ARRAY[startInclusive] == ARRAY[endInclusive] ? 1 : 0;

if (result == 0) {
    return DP[startInclusive][endInclusive] = result;
}

int inner =  solve(startInclusive + 1, endInclusive - 1);

if (inner == result) {
    return DP[startInclusive][endInclusive] = result;
}

return DP[startInclusive][endInclusive] = 0;

📗 코드

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

import static java.lang.System.in;

// 팰린드롬?
public class Main {
    static int[][] DP = new int[2001][2001];
    static int N, M;
    static int[] ARRAY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        N = Integer.parseInt(br.readLine());
        ARRAY = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int[] query = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            sb.append(solve(query[0] - 1, query[1] - 1)).append("\n");
        }
        System.out.println(sb);
    }

    private static int solve(int startInclusive, int endInclusive) {
        if (startInclusive > endInclusive) return 0;

        if (startInclusive == endInclusive) return 1;
        if (endInclusive - startInclusive == 1) {
            return ARRAY[startInclusive] == ARRAY[endInclusive] ? 1 : 0;
        }

        if (DP[startInclusive][endInclusive] == 1) return DP[startInclusive][endInclusive];

        int result = ARRAY[startInclusive] == ARRAY[endInclusive] ? 1 : 0;

        if (result == 0) {
            return DP[startInclusive][endInclusive] = result;
        }

        int inner =  solve(startInclusive + 1, endInclusive - 1);

        if (inner == result) {
            return DP[startInclusive][endInclusive] = result;
        }

        return DP[startInclusive][endInclusive] = 0;
    }

}