b10942. 펠린드롬?

 

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

 

 

 

 

🔁 자바로 푸는 펠린드롬? 문제 풀이 (백준 10942)

 

 

📌 문제 개요

 

• 수열이 주어졌을 때, 특정 구간이 펠린드롬(회문)인지 빠르게 판별해야 하는 문제입니다.
• 질의가 최대 100만 번까지 주어지므로, 단순한 비교로는 시간 초과가 발생합니다.

 

---

 

💡 예제 입력

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

 

예제 출력

1  
0  
1  
1

 

---

 

🛠 알고리즘 접근 방식

 

이 문제는 DP(Dynamic Programming) 을 활용해

모든 가능한 구간에 대해 펠린드롬 여부를 미리 계산한 뒤,

질의에 대해 빠르게 응답하는 구조로 풀 수 있습니다.

 

---

 

✅ 핵심 아이디어

 

• isAns[s][e] = true if arr[s] == arr[e] and isAns[s+1][e-1] == true
• 1글자, 2글자짜리 구간은 직접 비교로 초기화
• 이후 길이 3 이상인 구간은 점화식으로 채워나감

 

---

 

🧾 코드 해설

 

 

🎯 입력 및 배열 초기화

int N = Integer.parseInt(br.readLine());
int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
boolean[][] isAns = new boolean[N][N];

 

---

 

✏️ 1글자, 2글자 구간 초기화

for (int i = 0 ; i < N ; i++) {
    isAns[i][i] = true;
    if(i != N-1 && arr[i] == arr[i+1]) isAns[i][i+1] = true;
}

 

• 자기 자신 하나는 항상 펠린드롬
• 바로 옆 숫자가 같다면 길이 2의 펠린드롬

 

---

 

🔁 길이 3 이상 구간 채우기 (DP)

for (int len = 2; len < N; len++) {
    for (int s = 0; s + len < N; s++) {
        int e = s + len;
        if (arr[s] == arr[e] && isAns[s + 1][e - 1]) {
            isAns[s][e] = true;
        }
    }
}

 

• 점점 길어지는 구간을 확인하며,
• 양 끝이 같고, 안쪽이 펠린드롬이면 전체도 펠린드롬

 

---

 

📥 질의 처리

int M = Integer.parseInt(br.readLine());
for(int i = 0; i < M; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken())-1;
    int b = Integer.parseInt(st.nextToken())-1;
    sb.append(isAns[a][b]?1:0).append("\n");
}

 

• 미리 계산한 isAns를 이용하여 O(1) 시간으로 질의에 답변

 

---

 

✅ 핵심 포인트 요약

포인트	설명
DP 사용	중복 연산 없이 모든 구간에 대한 회문 여부 사전 계산
2차원 배열	isAns[start][end]로 구간 관리
O(N²) 사전 처리 + O(1) 질의	매우 효율적인 시간복잡도 구성
오프셋 주의	입력은 1-indexed → 내부 배열은 0-indexed

 

---

 

🎯 결론: 구간 회문 판별은 미리 준비하자

 

이 문제는 구간에 대한 반복 질의가 많은 경우,

정답을 미리 계산해놓는 전략(DP + 메모이제이션)이 매우 강력하다는 것을 보여줍니다.