문제 개요
문자열 s가 주어졌을 때, 이 문자열의 문자들을 재배열하여 만들 수 있는 모든 회문(팰린드롬) 순열을 중복 없이 찾는 것이 이번 문제의 목표입니다. 만약 회문 순열이 하나도 존재하지 않는다면 빈 결과를 반환하면 됩니다.
예를 들어 입력이 "aabb"라면, 만들 수 있는 회문 순열은 ["abba", "baab"] 두 가지입니다.
접근 방법
이 문제는 백트래킹(backtracking) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 문자가 몇 번 등장하는지 개수를 먼저 셉니다.
- 회문이 되려면 홀수 개로 등장하는 문자가 최대 1개여야 합니다. 홀수 개 문자가 2개 이상이면 회문 순열 자체가 불가능하므로 즉시 빈 결과를 반환합니다.
- 문자열의 왼쪽 끝과 오른쪽 끝에 같은 문자를 동시에 배치하며 재귀적으로 탐색합니다.
알고리즘 단계
결과를 저장할 배열 ret을 준비하고, 문자열 s, 남은 길이 sz, 문자별 개수를 담은 unordered_map m, 현재 인덱스 idx를 받는 solve() 함수를 다음과 같이 정의합니다.
- 종료 조건: sz가 0이 되면 완성된 문자열 s를 ret에 추가하고 함수를 종료합니다.
- evenFound 플래그를 false로 초기화하고, 이번 자리에서 이미 처리한 문자를 추적할 집합 visited를 준비합니다.
- 맵 m의 모든 (문자, 개수) 쌍을 순회하면서 다음을 수행합니다.
- 개수가 0이면 더 이상 사용할 수 없는 문자이므로 건너뜁니다.
- 개수가 1이면 이 문자를 oddChar(회문의 중앙에 놓일 유일한 후보)로 기록해 둡니다.
- 개수가 2 이상이고 아직 처리하지 않은 문자라면:
- s[idx]와 s[문자열 길이 − 1 − idx] 위치에 해당 문자를 배치합니다.
- evenFound를 true로 설정합니다.
- 맵에서 해당 문자의 개수를 2만큼 줄인 뒤, solve(s, sz − 2, m, idx + 1)을 재귀 호출합니다.
- 재귀가 끝나면 개수를 다시 2만큼 늘려 원상태로 복구합니다(백트래킹).
- 해당 문자를 visited에 추가하여 같은 문자의 중복 배치를 방지합니다.
- 순회가 끝난 뒤 evenFound가 false라면(짝수 개 문자를 배치하지 못했다면), oddChar를 s[idx]에 배치하고 solve(s, sz − 1, m, idx + 1)을 호출합니다. 이는 홀수 개 문자가 중앙에 놓이는 경우를 처리하는 단계입니다.
메인 함수(generatePalindromes)에서는 다음 작업을 수행합니다.
- 문자별 개수를 저장할 맵 cnt를 만들고, 문자열의 각 문자를 세어 기록합니다. 동시에 '*' 문자로 채운 임시 문자열 temp를 생성합니다.
- 개수가 홀수인 문자의 수 oddCnt를 계산합니다.
- oddCnt가 1보다 크면 회문 순열이 불가능하므로 빈 ret을 반환합니다.
- solve(temp, n, cnt)를 호출한 뒤 ret을 반환합니다.
예제 코드
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<string> ret;
void solve(string s, int sz, unordered_map<char,int>& m, int idx = 0){
if (sz == 0) {
ret.push_back(s);
return;
}
bool evenFound = false;
char oddChar;
unordered_map<char, int>::iterator it = m.begin();
set<char> visited;
while (it != m.end()) {
if (!it->second) {
it++;
continue;
}
else if (it->second == 1) {
oddChar = it->first;
}
else {
if (visited.count(it->first))
continue;
s[idx] = it->first;
s[s.size() - 1 - idx] = it->first;
evenFound = true;
m[it->first] -= 2;
solve(s, sz - 2, m, idx + 1);
m[it->first] += 2;
visited.insert(it->first);
}
it++;
}
if (!evenFound) {
s[idx] = oddChar;
solve(s, sz - 1, m, idx + 1);
}
}
vector<string> generatePalindromes(string s){
unordered_map<char,int> cnt;
int n = s.size();
string temp = "";
for (int i = 0; i < n; i++) {
cnt[s[i]]++;
temp += "*";
}
int oddCnt = 0;
unordered_map<char, int>::iterator it = cnt.begin();
while (it != cnt.end()) {
oddCnt += (it->second & 1);
it++;
}
if (oddCnt > 1)
return ret;
solve(temp, n, cnt);
return ret;
}
};
int main(){
Solution ob;
print_vector(ob.generatePalindromes("aabb"));
}실행 결과
입력:
"aabb"
출력:
[baab, abba]
실행 결과를 보면 "aabb"로 만들 수 있는 회문 순열은 baab와 abba 두 가지뿐이라는 것을 확인할 수 있습니다. 문자별 개수를 미리 검사해 불가능한 경우를 조기에 걸러내고, 양쪽 끝에서부터 대칭적으로 문자를 채워 나가는 방식 덕분에 중복 없이 모든 회문 순열을 효율적으로 생성할 수 있습니다.