C++로 문자열의 모든 회문 순열 출력하기

이 문제에서는 하나의 문자열이 주어지며, 해당 문자열의 문자들을 재배열하여 만들 수 있는 모든 회문(팰린드롬) 순열을 출력해야 합니다.

예시를 통해 문제를 살펴보겠습니다.

입력 − string = 'aabb'

출력 − abba baab

'aabb'의 문자들을 재배치하면 'abba'와 'baab'라는 두 가지 회문을 만들 수 있습니다.

문제 해결 접근 방법

이 문제를 해결하려면 문자열의 문자들을 하나씩 활용하여 만들 수 있는 모든 회문 문자열을 생성해야 합니다. 전체 과정은 다음과 같습니다.

1단계 − 문자열로 회문을 만들 수 있는지 먼저 확인합니다. 각 문자의 등장 횟수를 세어, 길이가 짝수인 문자열은 모든 문자가 짝수 번 나타나야 하며, 길이가 홀수인 문자열은 정확히 한 문자만 홀수 번 나타나야 합니다. 조건을 충족하지 못하면 'Not Possible'을 출력합니다.

2단계 − 회문 생성이 가능하다면 문자열을 절반으로 나누고, 각 문자를 사전순으로 선택하여 왼쪽 절반을 구성합니다.

3단계 − 왼쪽 절반으로 만든 순열들을 차례대로 순회하면서, 짝수 길이 문자열은 절반을 뒤집어 뒤에 붙이고, 홀수 빈도의 문자가 있는 경우에는 해당 문자를 가운데 배치하여 회문을 완성합니다.

4단계 − 생성된 모든 회문을 출력합니다.

알고리즘 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define M 26
bool isPalindrome(string str, int* freq){
    memset(freq, 0, M * sizeof(int));
    int l = str.length();
    for (int i = 0; i < l; i++)
        freq[str[i] - 'a']++;
    int odd = 0;
    for (int i = 0; i < M; i++)
        if (freq[i] % 2 == 1)
            odd++;
    if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
        return true;
    else
        return false;
}
string reverse(string str){
    string rev = str;
    reverse(rev.begin(), rev.end());
    return rev;
}
void generatePalindromePermutation(string str){
    int freq[M];
    if (!isPalindrome(str, freq))
        return;
    int l = str.length();
    string half ="";
    char oddC;
    for (int i = 0; i < M; i++) {
        if(freq[i] % 2 == 1)
            oddC = i + 'a';
        half += string(freq[i] / 2, i + 'a');
    }
    string palindrome;
    do {
        palindrome = half;
        if (l % 2 == 1)
            palindrome += oddC;
        palindrome += reverse(half);
        cout<<palindrome<<endl;
    }
    while (next_permutation(half.begin(), half.end()));
}
int main() {
    string str="abab";
    cout<<"All palindrome permutations of "<<str<<" are :\n";
    generatePalindromePermutation(str);
    return 0;
}

출력 결과

All palindrome permutations of abab are :
abba
baab

코드 설명

isPalindrome 함수는 각 알파벳 문자의 빈도를 계산하여 회문 생성 가능 여부를 판단합니다. generatePalindromePermutation 함수는 왼쪽 절반을 구성한 뒤 next_permutation을 통해 사전순으로 모든 순열을 생성하고, 각 순열에 대해 뒤집은 절반(필요한 경우 중간 문자 포함)을 이어 붙여 완전한 회문을 만들어 출력합니다. 이 방식은 중복 없이 사전순으로 회문 순열을 얻을 수 있다는 장점이 있습니다.