문제 소개
이 문제에서는 길이가 n인 문자열이 하나 주어집니다. 우리가 해야 할 일은 해당 문자열의 문자들을 재배치하여 만들 수 있는 모든 회문(palindrome) 순열을 찾아 알파벳 순서(사전순, lexicographical order)대로 출력하는 것입니다. 만약 주어진 문자열의 문자들로는 어떤 회문도 만들 수 없다면 '-1'을 출력하면 됩니다.
예시를 통해 문제를 더 자세히 살펴보겠습니다.
입력: string = "abcba" 출력: abcba bacab
"abcba"의 문자들(a 2개, b 2개, c 1개)로 만들 수 있는 회문은 위의 두 가지뿐이며, 결과는 사전순으로 정렬되어 출력됩니다.
해결 접근 방식
이 문제를 해결하는 방법은 크게 두 가지입니다.
- 만들 수 있는 모든 회문을 구한 뒤, 이를 사전순으로 정렬하여 출력한다.
- 사전순으로 가장 앞선 첫 번째 회문을 먼저 찾고, 그다음부터는 현재 회문보다 바로 다음(사전순)에 오는 회문을 순차적으로 찾아 나간다.
두 번째 방법이 훨씬 효율적이므로, 이 글에서는 두 번째 방법을 사용합니다.
알고리즘 단계
1단계 — 문자열에 등장하는 각 문자의 빈도수(frequency)를 계산하여 저장합니다.
2단계 — 해당 문자열로 회문을 만들 수 있는지 검사합니다. 회문이 성립하려면 홀수 번 등장하는 문자가 최대 1개여야 합니다(문자열 길이가 짝수라면 아예 없어야 합니다). 만들 수 없다면 안내 메시지 또는 '-1'을 출력하고 종료합니다.
3단계 — 짝수 번 등장하는 문자들은 절반씩 나누어 왼쪽 절반과 오른쪽 절반에 대칭으로 배치하고, 홀수 번 등장하는 문자 하나는 정중앙에 배치합니다. 즉, left_half + odd_char + reverse(left_half) 형태의 문자열을 만듭니다. 이렇게 하면 사전순으로 가장 앞선 첫 번째 회문을 얻을 수 있습니다.
4단계 — 현재 회문의 왼쪽 절반에 '다음 순열(next permutation)' 기법을 적용해 그다음으로 큰 회문을 찾고, 오른쪽 절반은 왼쪽 절반의 거울상으로 갱신합니다. 더 이상 다음 회문이 없을 때까지 반복하며 출력합니다.
C++ 구현 예제
아래는 위 개념을 구현한 전체 프로그램입니다.
#include <iostream>
#include <string.h>
using namespace std;
const char MAX_CHAR = 26;
void countFreq(char str[], int freq[], int n){
for (int i = 0; i < n; i++)
freq[str[i] - 'a']++;
}
bool canMakePalindrome(int freq[], int n){
int count_odd = 0;
for (int i = 0; i < 26; i++)
if (freq[i] % 2 != 0)
count_odd++;
if (n % 2 == 0) {
if (count_odd > 0)
return false;
else
return true;
}
if (count_odd != 1)
return false;
return true;
}
bool isPalimdrome(char str[], int n){
int freq[26] = { 0 };
countFreq(str, freq, n);
if (!canMakePalindrome(freq, n))
return false;
char odd_char;
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 != 0) {
freq[i]--;
odd_char = (char)(i + 'a');
break;
}
}
int front_index = 0, rear_index = n - 1;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
char ch = (char)(i + 'a');
for (int j = 1; j <= freq[i] / 2; j++) {
str[front_index++] = ch;
str[rear_index--] = ch;
}
}
}
if (front_index == rear_index)
str[front_index] = odd_char;
return true;
}
void reverse(char str[], int i, int j){
while (i < j) {
swap(str[i], str[j]);
i++;
j--;
}
}
bool nextPalindrome(char str[], int n){
if (n <= 3)
return false;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (str[i] < str[i + 1])
break;
if (i < 0)
return false;
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (str[j] > str[i] && str[j] < str[smallest])
smallest = j;
swap(str[i], str[smallest]);
swap(str[n - i - 1], str[n - smallest - 1]);
reverse(str, i + 1, mid);
if (n % 2 == 0)
reverse(str, mid + 1, n - i - 2);
else
reverse(str, mid + 2, n - i - 2);
return true;
}
void printAllPalindromes(char str[], int n){
if (!(isPalimdrome(str, n))) {
cout<<"-1";
return;
}
do {
cout<<str<<endl;
} while (nextPalindrome(str, n));
}
int main(){
char str[] = "abccba";
int n = strlen(str);
cout<<"가능한 회문 목록 :\n";
printAllPalindromes(str, n);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
가능한 회문 목록 : abccba acbbca baccab bcaacb cabbac cbaabc
코드 설명
- countFreq() — 문자열의 각 문자(a~z)가 몇 번 등장하는지 freq 배열에 저장합니다.
- canMakePalindrome() — 홀수 번 등장하는 문자의 개수를 세어, 문자열 길이가 짝수일 때는 0개, 홀수일 때는 정확히 1개여야 회문 생성이 가능함을 판별합니다.
- isPalimdrome() — 회문 생성 가능 여부를 확인한 뒤, 입력 배열 str을 사전순으로 가장 앞선 회문 형태로 직접 변환합니다. 짝수 빈도 문자들은 앞뒤 대칭으로 채우고, 홀수 문자는 중앙에 배치합니다.
- reverse() — 지정된 구간의 문자열을 뒤집는 보조 함수입니다.
- nextPalindrome() — 현재 회문의 왼쪽 절반에 다음 순열 알고리즘을 적용하여 사전순으로 다음에 오는 회문을 생성합니다. 더 이상 다음 회문이 없으면 false를 반환합니다.
- printAllPalindromes() — 회문 생성이 불가능하면 "-1"을 출력하고, 가능하면 do-while 루프를 통해 모든 회문을 순서대로 출력합니다.
마무리
이 알고리즘은 전체 순열을 일일이 생성·검사하지 않고 회문만을 대상으로 다음 순열을 찾기 때문에, 모든 순열을 무작위로 확인하는 방식보다 훨씬 효율적입니다. 각 회문을 생성하는 데 O(n)의 시간이 걸리며, 전체 실행 시간은 만들 수 있는 회문의 개수에 비례합니다.