C++로 문자열에서 소수 길이 회문 부분 문자열 개수 구하기

이 튜토리얼에서는 주어진 문자열 안에서 길이가 소수(prime)인 회문(palindrome) 부분 문자열의 개수를 구하는 프로그램을 다룹니다.

예를 들어 하나의 문자열이 입력으로 주어졌을 때, 우리의 목표는 그 문자열의 모든 부분 문자열 중에서 회문이면서 동시에 길이가 소수인 것들의 개수를 세는 것입니다.

접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

1단계: 소수 판별 (에라토스테네스의 체)

부분 문자열의 길이는 최대 문자열 전체 길이까지 가능하므로, 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 2부터 문자열 길이까지의 수 중에서 소수를 미리 구해 둡니다. 이렇게 하면 각 길이가 소수인지 O(1) 시간에 확인할 수 있습니다.

2단계: 회문 검사 및 개수 세기

각 소수 길이 j에 대해, 문자열에서 길이가 j인 모든 부분 문자열을 순회하면서 회문 여부를 검사합니다. 회문 검사는 두 포인터(two pointer) 기법을 사용해 양쪽 끝에서부터 중앙으로 이동하며 문자를 비교하는 방식으로 수행합니다.

C++ 구현 예제

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

// 회문 여부 검사 함수
bool if_palin(string str, int i, int j){
    while (i < j) {
        if (str[i] != str[j])
            return false;
        i++;
        j--;
    }
    return true;
}

// 소수 길이를 가지는 회문 부분 문자열 개수 세기
int count_prime(string str, int len){
    bool prime[len + 1];
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;

    // 에라토스테네스의 체로 소수 계산
    for (int p = 2; p * p <= len; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= len; i += p)
                prime[i] = false;
        }
    }

    int count = 0;
    // 각 소수 길이에 대해 모든 부분 문자열 검사
    for (int j = 2; j <= len; j++) {
        if (prime[j]) {
            for (int i = 0; i + j - 1 < len; i++) {
                if (if_palin(str, i, i + j - 1))
                    count++;
            }
        }
    }
    return count;
}

int main(){
    string s = "abccc";
    int len = s.length();
    cout << count_prime(s, len);
    return 0;
}

실행 결과

3

동작 과정 살펴보기

입력 문자열이 "abccc"(길이 5)일 때, 소수 길이는 2, 3, 5입니다.

• 길이 2: "ab", "bc", "cc", "cc" 중 회문은 "cc" 두 개 → 2개
• 길이 3: "abc", "bcc", "ccc" 중 회문은 "ccc" → 1개
• 길이 5: "abccc"는 회문이 아님 → 0개

따라서 최종 결과는 3이 됩니다.

시간 복잡도 분석

소수 길이마다 모든 시작 위치에 대해 회문 검사를 수행하므로, 최악의 경우 시간 복잡도는 O(n³)에 근사합니다(n은 문자열 길이). 문자열이 짧은 경우에는 충분히 실용적이지만, 더 긴 입력에는 Manacher's 알고리즘 등으로 각 위치별 회문 정보를 미리 계산해 최적화할 수 있습니다.