C++ 문자열에서 문자를 제거하거나 재배치하여 만들 수 있는 가장 긴 회문 찾기

개념

주어진 문자열에서 문자를 일부 제거하거나 순서를 재배치하여 만들 수 있는 가장 긴 회문(palindrome)을 구하는 문제입니다. 최장 길이의 회문이 여러 개 존재할 수 있는데, 이 경우 그중 하나만 출력하면 됩니다.

입력 · 출력 예시

예시 1

입력:

pqr

출력:

p 또는 q 또는 r

모든 문자가 한 번씩만 등장하므로, 어떤 단일 문자든 길이 1의 회문이 됩니다.

예시 2

입력:

ppqqrr

출력:

pqrrqp 또는 qprrpq 또는 rqppqr 등

길이 6의 회문을 만들 수 있으며, 가능한 조합은 여러 가지입니다.

예시 3

입력:

pqp

출력:

pqp

이미 회문인 경우 그대로 두는 것이 최선입니다.

풀이 접근 방법

모든 회문 문자열은 beg(앞부분) + mid(중간) + end(뒷부분)의 세 부분으로 나눌 수 있습니다.

홀수 길이(2n+1): beg는 처음 n개 문자, mid는 딱 1개 문자(n+1번째), end는 마지막 n개 문자로 구성됩니다.
짝수 길이(2n): mid는 항상 비어 있습니다.
회문이 되려면 end는 반드시 beg의 역순이어야 합니다.

문자를 자유롭게 재배치할 수 있으므로 입력 문자열의 원래 순서는 중요하지 않습니다. 따라서 다음과 같은 전략을 사용합니다.

먼저 입력 문자열에서 각 문자의 등장 빈도를 계산합니다.
짝수 번(2n번) 등장한 문자는 n개는 beg에, 나머지 n개는 end에 배치하여 회문 구조를 유지합니다.
홀수 번(2n+1번) 등장한 문자 중 하나는 mid에 배치하고, 남은 2n개는 반으로 나누어 앞뒤에 추가합니다. mid에는 하나의 문자만 들어갈 수 있으므로, 홀수 빈도 문자가 여럿이라면 마지막 문자로 덮어쓰게 됩니다.

C++ 구현 코드

// C++ 프로그램: 주어진 문자열에서 문자를 제거하거나
// 재배치하여 만들 수 있는 가장 긴 회문을 찾습니다
#include <bits/stdc++.h>
using namespace std;

// 주어진 문자열에서 문자를 제거하거나 재배치하여
// 만들 수 있는 가장 긴 회문을 찾는 함수
string findLongestPalindrome(string str1){
    // 문자열 내 각 문자의 빈도를 저장할 배열
    int count1[256] = { 0 };
    // 입력 문자열에서 각 문자의 빈도 계산
    for (int i = 0; i < str1.size(); i++)
        count1[str1[i]]++;
    // 모든 회문 문자열은 세 부분으로 구성됩니다.
    // beg1 + mid1 + end1
    string beg1 = "", mid1 = "", end1 = "";
    // 이 풀이는 문자열에 소문자만 포함되어 있다고 가정합니다.
    // 필요하면 다른 문자 집합으로도 쉽게 확장할 수 있습니다.
    for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
        // 현재 문자의 빈도가 홀수인 경우
        if (count1[ch1] & 1){
            // mid1에는 한 문자만 저장됩니다.
            // 다음 홀수 빈도 문자를 만나면 덮어써집니다.
            mid1 = ch1;
            // 현재 문자를 다시 처리할 수 있도록
            // 빈도를 1 줄여 짝수로 만듭니다.
            count1[ch1--]--;
        }
        // 현재 문자의 빈도가 짝수인 경우
        else{
            // 빈도가 n(짝수)이면 n/2개는 beg에,
            // 나머지 n/2개는 end를 구성합니다.
            for (int i = 0; i < count1[ch1]/2 ; i++)
                beg1.push_back(ch1);
        }
    }
    // end는 beg의 역순입니다.
    end1 = beg1;
    reverse(end1.begin(), end1.end());
    // 회문 문자열을 반환합니다.
    return beg1 + mid1 + end1;
}

// 드라이버 코드
int main(){
    string str1 = "pqqprrs";
    cout << findLongestPalindrome(str1);
    return 0;
}

실행 결과

pqrsrqp

입력 "pqqprrs"에서 p, q, r은 각각 2번, s는 1번 등장합니다. 따라서 beg = "pqr", mid = "s", end = "rqp"가 되어 길이 7의 회문 "pqrsrqp"가 완성됩니다.

복잡도 분석

시간 복잡도: O(n) — 문자열을 한 번 순회해 빈도를 계산하고, 알파벳 26자를 확인합니다.
공간 복잡도: O(1) 추가 공간(출력 문자열 제외) — 크기 256의 고정 빈도 배열만 사용합니다.