문자열이 여러 개 담긴 배열이 있을 때, 이 문자열들을 서로 다른 순서로 배치하는 모든 순열(permutation)을 각 줄에 출력해야 하는 경우가 있습니다.
예를 들어 입력이 ["abc", "def", "ghi"]라면, 출력은 다음과 같습니다.
abc def ghi abc ghi def def abc ghi def ghi abc ghi abc def ghi def abc
해결 접근 방식
이 문제는 사전순으로 다음 순열을 생성하는 next_permutation() 함수를 직접 구현하여 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.
next_permutation() 함수의 동작 원리
- 배열의 뒤쪽부터 앞쪽으로 탐색하면서, 현재 요소
s[i]가 바로 앞 요소s[i-1]보다 큰 지점(오름차순이 깨지는 지점)을 찾습니다. - 그 지점을 찾으면,
s[i-1]보다 큰 값들 중 가장 작은 요소와 교환(swap)합니다. - 교환한 위치 뒤쪽의 부분 배열을 오름차순으로 정렬하기 위해 좌우 대칭으로 뒤집습니다(reversal).
- 새로운 순열을 만들었다면
1을 반환하고, 더 이상 다음 순열이 없다면 배열을 원래 상태로 되돌린 후0을 반환합니다.
메인 함수의 처리 흐름
do-while반복문을 사용하여 현재 순열을 먼저 출력합니다.- 각 문자열을 공백으로 구분하여 출력하고, 마지막 문자열 뒤에는 줄바꿈 문자를 출력합니다.
next_permutation()이0을 반환할 때까지 위 과정을 반복합니다.
C 코드 구현
아래는 전체 동작을 보여주는 완전한 C 코드입니다.
#include <stdio.h>
#include <string.h>
int next_permutation(int n, char **s){
for (int i = n - 1; i > 0; i--)
if (strcmp(s[i], s[i - 1]) > 0){
int j = i + 1;
for (; j < n; j++)
if (strcmp(s[j], s[i - 1]) <= 0)
break;
char *t = s[i - 1];
s[i - 1] = s[j - 1];
s[j - 1] = t;
for (; i < n - 1; i++, n--){
t = s[i];
s[i] = s[n - 1];
s[n - 1] = t;
}
return 1;
}
for (int i = 0; i < n - 1; i++, n--){
char *t = s[i];
s[i] = s[n - 1];
s[n - 1] = t;
}
return 0;
}
int main(){
char *strings[] = {"abc", "def", "ghi"};
int n = 3;
do{
for (int i = 0; i < n; i++)
printf("%s%c", strings[i], i == n - 1 ? '\n' : ' ');
} while (next_permutation(n, strings));
}입력
{"abc", "def", "ghi"}출력
abc def ghi abc ghi def def abc ghi def ghi abc ghi abc def ghi def abc
정리
이 방식은 재귀 호출 없이 반복문만으로 모든 순열을 사전순(lexicographic order)으로 생성한다는 장점이 있습니다. 시간 복잡도는 순열의 총 개수인 O(n!)에 비례하며, 각 순열을 생성하는 데 드는 추가 비용은 O(n) 수준입니다. 문자열 비교에는 strcmp()를 사용하므로, 문자열 배열에 대해서도 정확하게 동작합니다.