C++로 문자열 속 특수 팰린드롬 개수 구하기

문제 개요

문자열 str이 주어졌을 때, 길이가 1보다 큰 특수 팰린드롬(special palindrome) 부분 문자열의 개수를 구하는 것이 목표입니다. 여기서 특수 팰린드롬이란 모든 문자가 동일하거나, 가운데 문자만 다른 문자열을 의미합니다.

예를 들어 문자열이 "baabaa"라면, 원본 문자열의 부분 문자열 중 특수 팰린드롬에 해당하는 것은 "aa", "aabaa", "aba", "aa"입니다.

예제로 이해하기

입력 − str = "abccdcdf"

출력 − 문자열 내 특수 팰린드롬의 개수: 3

설명 − 특수 팰린드롬에 해당하는 부분 문자열은 "cc", "cdc", "dcd"입니다.

입력 − str = "baabaab"

출력 − 문자열 내 특수 팰린드롬의 개수: 4

설명 − 특수 팰린드롬에 해당하는 부분 문자열은 "aa", "aabaa", "aba", "aa"입니다.

알고리즘 접근 방식

알파벳으로 이루어진 문자열을 만들고 길이를 계산한 뒤, 이후 처리를 위해 함수에 데이터를 전달합니다.
임시 변수 count와 i를 선언하고 0으로 초기화합니다.
문자열 길이와 같은 크기의 배열을 선언하고 0으로 초기화합니다.
i가 문자열 길이보다 작은 동안 WHILE 반복문을 수행합니다.
반복문 안에서 total을 1로, j를 i + 1로 설정합니다.
str[i]와 str[j]가 같고 j가 문자열 길이보다 작은 동안 내부 WHILE 반복문을 수행합니다.
반복문 안에서 total과 j를 각각 1씩 증가시킵니다.
count에 total × (total + 1) ÷ 2를 더하고, arr[i]에 total을 저장한 후 i를 j로 갱신합니다. 이 과정은 연속된 같은 문자 구간에서 만들 수 있는 부분 문자열의 개수를 한 번에 계산합니다.
j가 1부터 문자열 길이까지 FOR 반복문을 수행합니다.
str[j] == str[j-1]이라면 arr[j]를 arr[j-1]로 설정합니다.
변수 temp를 str[j-1]로 지정하고, j가 0보다 크고 문자열 길이보다 1 작으며, temp == str[j+1]이면서 str[j] != temp인 경우(예: "aba", "cdc"처럼 가운데 문자만 다른 경우) count에 min(arr[j-1], arr[j+1])을 더합니다.
마지막으로 count에서 문자열 길이를 뺍니다. 이는 길이 1짜리 문자 하나도 '모든 문자가 같은' 팰린드롬으로 카운트되므로, 문제 조건(길이 2 이상)에 맞게 제외하기 위함입니다.
count를 반환하고 결과를 출력합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
    int count = 0, i = 0;
    int arr[len] = { 0 };
    while (i < len){
        int total = 1;
        int j = i + 1;
        while (str[i] == str[j] && j < len){
            total++;
            j++;
        }
        count += (total * (total + 1) / 2);
        arr[i] = total;
        i = j;
    }
    for (int j = 1; j < len; j++){
        if (str[j] == str[j - 1]){
            arr[j] = arr[j - 1];
        }
        int temp = str[j - 1];
        if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
            count += min(arr[j-1], arr[j+1]);
        }
    }
    count = count - len;
    return count;
}
int main(){
    string str = "bcbaba";
    int len = str.length();
    cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

Count of special palindromes in a String are: 3

이 알고리즘은 문자열을 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 모든 부분 문자열을 일일이 검사하는 브루트 포스 방식(O(n²)~O(n³))보다 훨씬 효율적입니다.