이 글에서는 C++에서 문자열의 사전순(lexicographical order) 다음 순열을 생성하는 방법을 알아봅니다. C++ 표준 라이브러리가 제공하는 next_permutation() 함수를 활용하면 몇 줄의 코드만으로 손쉽게 구현할 수 있습니다.
사전순 다음 순열이란?
사전순 다음 순열이란 현재 문자열의 모든 문자를 사전식 순서로 재배치했을 때, 현재 값보다 바로 다음으로 큰 순열을 의미합니다. 예를 들어 "ACB"의 다음 순열은 "BAC"입니다. 반면 "BBB"나 "DCBA"처럼 이미 가장 마지막 순열인 경우에는 더 큰 순열이 존재하지 않으므로 다음 순열을 구할 수 없습니다.
next_permutation() 함수 사용하기
C++에서는 <algorithm> 헤더 파일에 정의된 next_permutation() 라이브러리 함수를 사용하면 됩니다. 이 함수는 지정한 범위의 요소들을 다음 순열로 변환하며, 다음 순열이 성공적으로 생성되면 true, 더 이상 다음 순열이 존재하지 않으면 false를 반환합니다.
예제 코드
#include <iostream>
#include <algorithm>
using namespace std;
main() {
string s = "DBAC";
for(int i = 0; i<5; i++) {
bool val = next_permutation(s.begin(), s.end());
if (val == false) {
cout << "No next permutation" << endl;
break;
} else
cout << "Next: " << s << endl;
}
}
실행 결과
Next: DBCA
Next: DCAB
Next: DCBA
No next permutation
동작 원리
next_permutation()은 시퀀스의 뒤쪽부터 탐색하여 오름차순이 유지되는 가장 긴 접미사(suffix)를 찾아냅니다. 전체가 내림차순으로 정렬되어 있다면 해당 시퀀스가 마지막 순열이라는 뜻이므로 함수는 false를 반환합니다. 그렇지 않은 경우, 접미사 바로 앞의 기준점(pivot)과 접미사 내에서 pivot보다 큰 값 중 가장 작은 값을 서로 교환한 뒤, 접미사 부분을 뒤집어 다음 순열을 완성합니다. 위 예제에서 "DBAC"는 "DBCA" → "DCAB" → "DCBA" 순으로 변환되며, "DCBA"는 내림차순 정렬 상태이므로 더 이상의 순열이 없다는 메시지가 출력됩니다.