이 문제에서는 하나의 문자열 str이 주어지며, 문자열에 포함된 문자들의 모든 조합을 사전순(lexicographical order)으로 출력해야 합니다.
문제 이해하기
예시를 통해 문제를 더 자세히 살펴보겠습니다.
입력: str = 'XYZ' 출력 : X XY XYZ XZ XZY Y YX YXZ YZ YZX Z ZX ZXY ZY ZYX
접근 방법
이 문제를 해결하려면 문자열 내 문자들의 모든 조합을 생성하여 출력해야 합니다. 이를 위해 다음과 같은 전략을 사용합니다.
- 맵(map) 자료구조를 사용하여 문자열의 각 문자와 그 빈도수를 저장합니다. 맵은 키를 기준으로 자동 정렬되므로, 별도의 정렬 작업 없이도 사전순 처리가 가능합니다.
- 백트래킹(backtracking) 기법을 활용하여 모든 조합을 체계적으로 탐색하고 추적합니다.
각 단계에서 사용 가능한 문자를 하나 선택하고, 결과 배열에 추가한 뒤 재귀적으로 다음 단계로 진행합니다. 해당 분기의 탐색이 끝나면 문자 개수를 복원하여 다른 조합도 탐색할 수 있도록 합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void printResult(char* result, int len);
void findstringCombination(char result[], char str[], int count[], int level, int size, int length);
void printCharCombination(string str);
int main(){
string str = "ABC";
cout<<"문자열의 문자 조합 :\n";
printCharCombination(str);
return 0;
}
void findstringCombination(char result[], char str[], int count[], int level, int size, int length){
if (level == size)
return;
for (int i = 0; i < length; i++) {
if (count[i] == 0)
continue;
count[i]--;
result[level] = str[i];
printResult(result, level);
findstringCombination(result, str, count, level + 1, size, length);
count[i]++;
}
}
void printCharCombination(string str){
map<char, int> mp;
for (int i = 0; i < str.size(); i++) {
if (mp.find(str[i]) != mp.end())
mp[str[i]] = mp[str[i]] + 1;
else
mp[str[i]] = 1;
}
char* input = new char[mp.size()];
int* count = new int[mp.size()];
char* result = new char[str.size()];
map<char, int>::iterator it = mp.begin();
int i = 0;
for (it; it != mp.end(); it++) {
input[i] = it->first;
count[i] = it->second;
i++;
}
int length = mp.size();
int size = str.size();
findstringCombination(result, input, count, 0, size, length);
}
void printResult(char* result, int len){
for (int i = 0; i <= len; i++)
cout<<result[i];
cout<<endl;
}코드 설명
printCharCombination함수는 입력 문자열의 각 문자 빈도를map<char, int>에 저장합니다. C++의 맵은 키가 오름차순으로 정렬되기 때문에, 중복 문자가 있어도 사전순 출력이 보장됩니다.findstringCombination함수는 백트래킹의 핵심 로직을 담당합니다. 현재 깊이(level)에서 사용 가능한 문자를 선택하고, 결과를 출력한 후 재귀 호출로 더 긴 조합을 만듭니다.count[i]++구문은 백트래킹 시 문자 사용 횟수를 원래대로 되돌려, 다른 경로의 조합 탐색이 가능하게 합니다.
출력 결과
위 코드를 실행하면 문자열 'ABC'의 모든 조합이 사전순으로 출력됩니다.
A AB ABC AC ACB B BA BAC BC BCA C CA CAB CB CBA
마무리
이 알고리즘은 맵과 백트래킹을 결합하여 중복 문자가 포함된 경우에도 정확하게 동작합니다. 시간 복잡도는 생성되는 조합의 총 개수에 비례하며, 문자열 길이가 n일 때 최대 O(n × n!) 수준입니다. 따라서 입력 문자열이 짧은 경우에 적합한 접근 방식입니다.