문자열의 순열(permutation)이란 주어진 문자열의 문자들을 다양한 방식으로 재배치하여 만들 수 있는 모든 조합을 의미합니다. 이번 튜토리얼에서는 C++의 표준 템플릿 라이브러리(STL)를 활용하여 주어진 문자열의 모든 순열을 출력하는 방법을 알아보겠습니다.
예시
입력 : s = "ADT" 출력 : "ADT", "ATD", "DAT", "DTA", "TAD", "TDA" 설명 : 위 출력 결과를 보면 모든 문자열이 입력 문자열에 포함된 동일한 세 개의 문자로 구성되어 있으며, 단순히 순서만 바뀐 형태입니다. 따라서 이들은 문자열의 순열 정의에 부합하며, 실제로 문자열 s에서 만들 수 있는 모든 가능한 순열입니다.
주어진 문자열의 모든 순열을 출력하는 방법은 크게 두 가지가 있습니다.
방법 1: rotate() 함수 활용
첫 번째 방법은 STL의 rotate() 함수를 사용하는 것입니다. 이 함수는 문자열을 회전시키는 역할을 하며, 여기에 재귀 호출을 결합하여 모든 순열을 출력할 수 있습니다.
동작 원리
재귀 함수는 문자열의 첫 번째 문자를 결과 문자열(ans)에 추가하고, 나머지 부분을 다음 호출에 전달합니다. 그런 다음 rotate()를 사용해 두 번째 문자를 첫 번째 위치로 옮긴 뒤 같은 과정을 반복합니다. 회전할 문자열이 비어 있으면 그동안 쌓인 ans가 하나의 완성된 순열이므로 이를 출력합니다.
C++ 코드
#include<bits/stdc++.h>
using namespace std;
void permutations(string s, string ans){
if(s.size() == 0) {
// 회전 대상 문자열이 비었다는 것은
// 하나의 순열이 ans에 완성되었음을 의미
cout << ans << "\n";
return ;
}
for(int i = 0; i < s.size(); i++){
permutations(s.substr(1), ans + s[0]);
// 첫 번째 문자를 ans에 추가하고,
// 인덱스 1부터의 나머지 문자열을 다음 호출에 전달
rotate(s.begin(), s.begin()+1, s.end());
// 두 번째 문자가 첫 번째로 오도록 회전
}
}
int main(){
string s = "ADT"; // 주어진 문자열
permutations(s, "");
return 0;
}출력 결과
ADT ATD DTA DAT TAD TDA
방법 2: next_permutation() 함수 활용
두 번째 방법은 STL의 next_permutation() 함수를 사용하는 것입니다. 이름 그대로 이 함수는 해당 문자열의 다음 순열이 존재하는지 확인하고, 존재하면 문자열을 다음 순열로 변환한 후 true를 반환하며, 더 이상 다음 순열이 없으면 false를 반환합니다.
이 함수는 사전순(lexicographic order)으로 다음 순열을 찾기 때문에, 모든 가능한 순열을 빠짐없이 얻으려면 먼저 문자열을 오름차순으로 정렬해야 합니다.
C++ 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
string s = "ADT"; // 주어진 문자열
sort(s.begin(), s.end()); // 문자열을 사전순으로 정렬
do{
cout << s << "\n"; // 순열 출력
}while(next_permutation(s.begin(), s.end())); // next_permutation이 false를 반환할 때까지 반복
return 0;
}출력 결과
ADT ATD DAT DTA TAD TDA
위 프로그램에서는 먼저 문자열을 정렬한 뒤, next_permutation() 함수를 통해 모든 가능한 순열을 순서대로 출력합니다. do-while 문을 사용했기 때문에 정렬된 초기 상태(첫 번째 순열)도 반드시 한 번 출력됩니다.
마무리
이번 튜토리얼에서는 C++의 STL을 활용하여 주어진 문자열의 모든 가능한 순열을 출력하는 방법을 살펴보았습니다. 재귀와 rotate()를 조합하는 방법과 next_permutation()을 사용하는 방법 두 가지를 배웠으며, 각 방식의 C++ 구현 코드와 함께 STL 핵심 함수들의 용도도 함께 익혔습니다. 두 방법 모두 시간 복잡도는 O(N × N!)로 동일하지만, next_permutation()을 활용한 방법이 코드가 더 간결하고 직관적이라는 점을 참고하시기 바랍니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.