[BOJ 10942 // C++] 팰린드롬?

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10942번 문제인 팰린드롬?이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

팰린드롬(palindrome; 회문)이란 앞에서부터 읽을 때랑 뒤에서부터 읽을 때 같게 읽히는 문자열을 의미한다.

 

이 문제에서는 미리 주어진 한자리 수로 이루어진 수열에서 두 수 s, e(단, s<=e)를 입력받아 s번째 숫자부터 e번째 숫자까지의 수열이 팰린드롬을 이루는지 확인해야한다.

 

여러 s와 e를 받아 처리하다보면 중복된 확인이 빈번히 일어나게 되는데, 이러한 중복을 줄이는 것이 이 문제를 푸는 것의 핵심이다.

 

어떤 수열이 팰린드롬을 이룬다면, 이 수열의 첫 항과 마지막 항을 제거한 나머지 또한 팰린드롬을 이룬다.

역으로, 어떤 수열이 첫항과 마지막 항이 같고, 첫 항과 마지막 항을 제거한 나머지 수열이 팰린드롬을 이룬다면 이 수열은 팰린드롬을 이룬다.

 

따라서, 주어진 수열에서, 가운데로 사용할 수 있는 길이 1, 2짜리 수열에서부터 각각의 수열을 (수열의 범위가 넘어가지 않을 때까지) 앞뒤로 숫자를 하나씩 붙여가면서 모든 가능한 팰린드롬 문자열의 시작점 및 끝점을 2차원 배열의 성분으로 하여 모든 부분문자열(substring)이 팰린드롬인지 아닌지 미리 저장할 수 있다.

이 배열이 있다면 이 문제에서 들어오는 10만개의 질문의 답을 바로 배열에서 꺼내 답할 수 있으므로, 문제를 해결할 수 있다.

 

그러나, 같은 상황에서 수열의 길이가 100만까지 커질 수 있는 11046번 문제(팰린드롬??)은 이 방법으로 해결할 수 없다.

수열의 길이가 더 길어진다면, Manacher's Algorithm을 이용해 모든 팰린드롬 부분문자열을 구하는 것이 좋다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int nums[2001]; // 수열을 저장
bool isPal[2001][2001]; // s번째 숫자부터 e번째 숫자까지가 팰린드롬을 이루는지 저장

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int x;
    for (int i = 1;i <= N;i++) {
        cin >> x; nums[i] = x;
    }
    int l, r;
    for (int i = 1;i <= N;i++) {
        l = i, r = i; // 홀수 길이 수열 판단
        while (l > 0 and r <= N) {
            if (nums[l] == nums[r]) isPal[l][r] = 1;
            else break;
            l--; r++;
        }
        l = i, r = i + 1;
        while (l > 0 and r <= N) { // 짝수 길이 수열 판단
            if (nums[l] == nums[r]) isPal[l][r] = 1;
            else break;
            l--; r++;
        }
    }
    int M; cin >> M;
    int s, e;
    for (int i = 0;i < M;i++) {
        cin >> s >> e;
        cout << isPal[s][e] << '\n';
    }
}