[BOJ/Java] 10942. 팰린드롬?

📌 [BOJ/Java] 10942. 팰린드롬?

🔗 문제 링크: 백준 10942번 - 팰린드롬?

---

📖 문제 해석

🔢 주어진 수열에서 특정 구간이 팰린드롬인지 판별하는 문제이다.
🛠️ 팰린드롬(Palindrome): 앞에서 읽어도 뒤에서 읽어도 같은 문자열 or 수열
❓ 여러 개의 질문(구간)이 주어지며, 각 구간이 팰린드롬인지 빠르게 판단해야 한다.

✅ 핵심 개념

• 단순하게 매번 확인하면 O(N) 연산이 필요하므로 비효율적
• DP(동적 계획법) 활용하여 중복 계산 최소화
• 구간 판별 문제이므로 "구간 DP"로 접근

---

🛠️ 풀이 과정

1️⃣ 입력 처리 및 초기화

• N개의 숫자를 입력받아 배열에 저장
• dp[i][j]를 사용하여 i부터 j까지의 구간이 팰린드롬인지 저장

2️⃣ DP 테이블 채우기

• dp[i][i] = true (길이 1짜리 구간은 항상 팰린드롬)
• dp[i][i+1] = (arr[i] == arr[i+1]) (길이 2짜리 구간은 두 숫자가 같으면 팰린드롬)
• 길이가 3 이상일 때:
  dp[i][j] = (arr[i] == arr[j]) && dp[i+1][j-1]

3️⃣ 질문에 빠르게 답하기

• dp[s][e] 값을 바로 출력하여 O(1) 시간 복잡도로 판별

---

💻 코드 구현 (Java)

import java.util.*;

public class Main {
    static int N, M;
    static int[] arr;
    static boolean[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        arr = new int[N + 1]; // 1-based index
        dp = new boolean[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }

        preprocess(); // DP 테이블 미리 채우기

        M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            sb.append(dp[s][e] ? "1\n" : "0\n");
        }

        System.out.print(sb);
    }

    public static void preprocess() {
        // 길이 1인 구간 (항상 팰린드롬)
        for (int i = 1; i <= N; i++) {
            dp[i][i] = true;
        }

        // 길이 2인 구간
        for (int i = 1; i < N; i++) {
            if (arr[i] == arr[i + 1]) {
                dp[i][i + 1] = true;
            }
        }

        // 길이 3 이상인 구간
        for (int len = 3; len <= N; len++) { // 부분 문자열 길이
            for (int i = 1; i + len - 1 <= N; i++) { // 시작 인덱스
                int j = i + len - 1; // 끝 인덱스
                if (arr[i] == arr[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
    }
}

---

⏱️ 시간 복잡도 분석

📌 O(N² + M) (최대 2500² + 10⁶ ≈ 625만 연산)
💡 DP 테이블 채우기 → O(N²)
💡 각 질의 처리 → O(1) (총 O(M))
🔥 N ≤ 2000이므로 충분히 해결 가능

---

💡 느낀점

✅ 구간 DP를 활용하는 좋은 문제
✅ 매번 직접 팰린드롬을 검사하면 O(N)씩 걸리지만, DP를 이용해 O(1)로 처리 가능
✅ 문자열이나 수열의 "구간 문제"는 DP 활용 가능성을 항상 고민해봐야 한다! 🚀