C++로 중복 문자가 있는 문자열의 모든 고유 순열 출력하기

문제 개요

이번 문제에서는 중복 문자가 포함될 수 있는 문자열이 주어졌을 때, 해당 문자열의 모든 고유한(distinct) 순열을 출력하는 것이 목표입니다.

예시를 통해 문제를 살펴보겠습니다.

입력: string = "XYZ"
출력: XYZ XZY YXZ YZX ZYX ZXY

문자열 "XYZ"에는 중복 문자가 없으므로 총 3! = 6가지의 순열이 모두 고유하게 출력됩니다. 만약 "AAB"처럼 중복 문자가 있다면, 동일한 결과가 여러 번 출력되지 않도록 중복을 제거한 순열만 출력해야 합니다.

해결 접근 방법

이 문제를 효율적으로 해결하려면 다음 순열(Next Permutation) 생성 알고리즘을 활용할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 먼저 문자열을 오름차순으로 정렬하여 사전순으로 가장 작은 순열부터 시작합니다.
2. 현재 순열을 출력한 뒤, 사전순으로 바로 다음에 오는 순열을 생성합니다.
3. 더 이상 다음 순열이 존재하지 않을 때까지(내림차순 정렬 상태가 될 때까지) 위 과정을 반복합니다.

다음 순열을 찾는 과정은 다음 단계로 진행됩니다.

- 문자열의 끝에서부터 왼쪽으로 탐색하면서, 자신보다 오른쪽에 있는 문자보다 작은 위치(i)를 찾습니다. 즉, str[i] < str[i+1]을 만족하는 가장 큰 i를 구합니다.
- 그런 위치가 없다면 현재 순열이 마지막 순열이므로 종료합니다.
- i 오른쪽 구간에서 str[i]보다 큰 문자 중 가장 작은 문자(ceil)를 찾아 str[i]와 교환합니다.
- i 이후의 부분 문자열을 다시 오름차순으로 정렬하여 다음 순열을 완성합니다.

이 방식은 중복 문자가 있어도 각 순열을 정확히 한 번씩만 생성하므로, 별도의 중복 검사 없이 고유한 순열만 출력할 수 있다는 장점이 있습니다.

구현 예제 코드

위 알고리즘을 C++로 구현한 프로그램입니다.

#include <string.h>
#include <iostream>
using namespace std;

int compare(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

void swapChar(char* a, char* b) {
    char t = *a;
    *a = *b;
    *b = t;
}

// first보다 큰 문자 중 가장 작은 문자(ceil)의 인덱스를 찾는 함수
int findCeil(char str[], char first, int l, int h) {
    int ceilIndex = l;
    for (int i = l + 1; i <= h; i++)
        if (str[i] > first && str[i] < str[ceilIndex])
            ceilIndex = i;
    return ceilIndex;
}

void printPermutations(char str[]) {
    int size = strlen(str);
    qsort(str, size, sizeof(str[0]), compare); // 오름차순 정렬
    bool isFinished = false;
    while (!isFinished) {
        cout << str << "\t"; // 현재 순열 출력
        int i;
        // 다음 순열이 가능한 위치 i 찾기
        for (i = size - 2; i >= 0; --i)
            if (str[i] < str[i + 1])
                break;
        if (i == -1)
            isFinished = true; // 마지막 순열이면 종료
        else {
            int ceilIndex = findCeil(str, str[i], i + 1, size - 1);
            swapChar(&str[i], &str[ceilIndex]);
            qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare);
        }
    }
}

int main() {
    char str[] = "SNGY";
    cout << "문자열 " << str << " 의 모든 순열 :\n";
    printPermutations(str);
    return 0;
}

실행 결과

문자열 SNGY 의 모든 순열 :
GNSY GNYS GSNY GSYN GYNS GYSN NGSY NGYS NSGY NSYG NYGS NYSG SGNY SGYN SNGY SNYG SYGN SYNG YGNS YGSN YNGS YNSG YSGN YSNG

마무리

이 알고리즘은 재귀 호출 없이 반복문만으로 모든 순열을 사전순으로 생성하며, 중복 문자가 포함된 경우에도 고유한 순열만 정확히 한 번씩 출력합니다. 시간 복잡도는 순열 하나를 생성할 때마다 정렬 연산이 포함되어 O(n log n)이며, 전체 순열 개수는 최대 n!개이므로 전체 실행 시간은 O(n! × n log n)입니다.