C++ 프로그램에서 substring[L…R]이 회문인지 확인하는 쿼리 문제 풀이

문자열 str과, 각각 두 값 L과 R로 구성된 Q개의 쿼리가 주어졌을 때, 부분 문자열 [L…R]이 회문(palindrome)인지 판별하는 프로그램을 작성하는 것이 이번 문제의 목표입니다.

문제 설명

각 쿼리에 대해 주어진 범위 L~R에 해당하는 부분 문자열을 만들고, 앞으로 읽으나 뒤로 읽으나 같은 회문인지 아닌지를 확인해야 합니다.

예제로 이해하기

입력

str = "abccbeba", Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}}

출력

Palindrome
Not Palindrome
Palindrome

설명

부분 문자열 [1...4] = "bccb" → 거꾸로 읽어도 "bccb"이므로 회문입니다.
부분 문자열 [0...6] = "abccbeb" → 뒤집으면 "bebccba"로 달라지므로 회문이 아닙니다.
부분 문자열 [4...6] = "beb" → 거꾸로 읽어도 "beb"이므로 회문입니다.

방법 1: 단순 비교(브루트 포스)

가장 직관적인 접근 방식은 쿼리 하나하나를 개별적으로 처리하는 것입니다. 쿼리가 들어올 때마다 인덱스 L부터 R까지의 부분 문자열을 추출한 뒤, 첫 번째 문자와 마지막 문자부터 차례로 비교하며 회문 여부를 검사합니다.

아래는 이 방식을 구현한 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;

// 주어진 문자열이 회문인지 확인하는 함수
bool isPalindrome(string str) {
    int length = str.length();
    for (int i = 0; i < length / 2; i++) {
        if (str[i] != str[length - i - 1])
            return false;
    }
    return true;
}

// 모든 쿼리를 처리하는 함수
void solveAllQueries(string str, int Q, int query[][2]) {
    for (int i = 0; i < Q; i++) {
        int L = query[i][0];
        int R = query[i][1];
        string sub = str.substr(L, R - L + 1); // L~R 범위의 부분 문자열 추출
        if (isPalindrome(sub))
            cout << "Palindrome\n";
        else
            cout << "Not Palindrome\n";
    }
}

int main() {
    string str = "abccbeba";
    int Q = 3;
    int query[3][2] = {{1, 4}, {0, 6}, {4, 6}};
    solveAllQueries(str, Q, query);
    return 0;
}

출력 결과:

Palindrome
Not Palindrome
Palindrome

이 방법은 구현이 매우 간단하지만, 쿼리 하나당 최대 O(N)의 시간이 소요되므로 전체 시간 복잡도는 O(Q × N)이 됩니다. 문자열이 길고 쿼리 수가 많아지면 비효율적일 수 있습니다.

방법 2: 동적 계획법(Dynamic Programming)

더 효율적인 해결책은 동적 계획법을 활용하는 것입니다. 2차원 DP 테이블을 미리 만들어 두면 이후 모든 쿼리를 상수 시간(O(1))에 처리할 수 있습니다.

• 정의: DP[i][j]는 부분 문자열 [i...j]가 회문이면 true(1), 아니면 false(0)를 저장합니다.
• 점화식: str[i] == str[j]이면서, (j − i ≤ 1이거나 DP[i+1][j−1]이 참)일 때 DP[i][j] = true입니다.

즉, 양 끝의 문자가 서로 같고 그 안쪽 부분 문자열 역시 이미 회문이라면 전체도 회문이라는 원리를 이용합니다.

아래는 동적 계획법을 적용한 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;

// 회문 여부를 저장하는 DP 테이블 계산
void computeDP(bool DP[][50], string &str) {
    int n = str.size();
    for (int i = 0; i < n; i++)          // 테이블 초기화
        for (int j = 0; j < n; j++)
            DP[i][j] = false;

    for (int j = 1; j <= n; j++) {       // 부분 문자열의 길이 j
        for (int i = 0; i <= n - j; i++) { // 시작 인덱스 i
            int end = i + j - 1;
            if (j <= 2)                    // 길이 1 또는 2인 경우
                DP[i][end] = (str[i] == str[end]);
            else                           // 길이 3 이상인 경우
                DP[i][end] = (str[i] == str[end]) && DP[i + 1][end - 1];
        }
    }
}

// 모든 쿼리를 처리하는 함수
void solveAllQueries(string str, int Q, int query[][2]) {
    bool DP[50][50];
    computeDP(DP, str);
    for (int i = 0; i < Q; i++) {
        if (DP[query[i][0]][query[i][1]])
            cout << "Palindrome\n";
        else
            cout << "Not Palindrome\n";
    }
}

int main() {
    string str = "abccbeba";
    int Q = 3;
    int query[3][2] = {{1, 4}, {0, 6}, {4, 6}};
    solveAllQueries(str, Q, query);
    return 0;
}

출력 결과:

Palindrome
Not Palindrome
Palindrome

시간 복잡도 비교

• 브루트 포스: 전처리 없음, 쿼리당 O(N) → 총 O(Q × N)
• 동적 계획법: 전처리 O(N²), 쿼리당 O(1) → 총 O(N² + Q)

따라서 쿼리 수가 많은 경우에는 동적 계획법이 훨씬 유리합니다. 단, DP 테이블 생성에 O(N²) 크기의 메모리가 필요하다는 점은 함께 고려해야 합니다.