이 문제에서는 길이가 n인 문자열이 주어지며, 문자열을 구성하는 문자들의 모든 순열(permutation)을 정렬된 순서, 즉 사전식(lexicographical) 순서로 출력해야 합니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력: 'XYZ'
출력: XYZ, XZY, YXZ, YZX, ZXY, ZYX
위 예제에서 볼 수 있듯이, 우리는 모든 순열을 사전식 순서(알파벳 오름차순)로 출력해야 합니다. 사전식 순서란 사전에서 단어가 배열되는 방식과 동일하게, 앞 문자부터 비교하여 알파벳 순으로 나열하는 방식을 의미합니다.
문제 해결 접근 방법
이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.
먼저 문자열을 알파벳 오름차순으로 정렬합니다. 정렬된 문자열이 바로 첫 번째 순열이 됩니다. 그다음에는 현재 순열보다 사전식 순서상 바로 다음에 오는 순열(next permutation)을 반복적으로 생성하며, 더 이상 다음 순열이 존재하지 않을 때까지 이 과정을 반복합니다.
다음 순열을 찾는 알고리즘은 다음 단계로 동작합니다.
1. 문자열의 뒤쪽부터 탐색하여 처음으로 str[i] < str[i+1]을 만족하는 위치 i를 찾습니다. 이러한 위치가 없다면 현재 순열이 마지막 순열이라는 의미이므로 종료합니다.
2. i보다 뒤쪽 구간에서 str[i]보다 큰 문자 중 가장 작은 문자(즉, str[i]보다 큰 값들 중 최솟값)의 위치를 찾아 str[i]와 교환(swap)합니다.
3. i 이후의 부분 문자열을 오름차순으로 정렬하여 가장 작은 순열을 만듭니다.
아래 코드를 통해 해결 방법을 더 명확히 이해할 수 있습니다.
예제 코드
#include<iostream>
#include<string.h>
using namespace std;
int compare(const void *a, const void * b){
return ( *(char *)a - *(char *)b );
}
void swap(char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}
int finduBound(char str[], char first, int l, int h) {
int ubound = l;
for (int i = l+1; i <= h; i++)
if (str[i] > first && str[i] < str[ubound])
ubound = i;
return ubound;
}
void generatePermutaion ( char str[] ) {
int size = strlen(str);
qsort( str, size, sizeof( str[0] ), compare );
bool isFinished = false;
while ( ! isFinished ) {
cout<<str<<"\t";
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
if ( i == -1 )
isFinished = true;
else {
int ubound = finduBound( str, str[i], i + 1, size - 1 );
swap( &str[i], &str[ubound] );
qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
}
}
}
int main() {
char str[] = "NOPQ";
cout<<"Permutation in Sorted order :\n";
generatePermutaion(str);
return 0;
}실행 결과
Permutation in Sorted order : NOPQ NOQP NPOQ NPQO NQOP NQPO ONPQ ONQP OPNQ OPQN OQNP OQPN PNOQ PNQO PONQ POQN PQNO PQON QNOP QNPO QONP QOPN QPNO QPON
코드 설명
generatePermutaion 함수는 먼저 qsort를 사용해 입력 문자열을 오름차순으로 정렬한 후, while 루프를 통해 각 순열을 출력하고 다음 순열을 생성합니다. finduBound 함수는 교환할 후보 문자 중 str[i]보다 크면서도 가장 작은 값을 찾는 역할을 하며, 이를 통해 항상 사전식 순서대로 다음 순열이 생성되도록 보장합니다.
참고로 C++ 표준 라이브러리(STL)를 사용한다면 std::next_permutation 함수를 활용하여 훨씬 간결하게 동일한 결과를 얻을 수 있습니다. std::next_permutation은 내부적으로 위에서 설명한 것과 같은 알고리즘을 사용하므로, 직접 구현한 코드와 동일한 순서로 순열을 생성합니다.