Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 중복 문자를 허용하는 문자열의 고유한 정렬된 순열 출력하기

문제 개요

이번 프로그래밍 문제에서는 하나의 문자열이 주어지며, 해당 문자열의 문자들로 만들 수 있는 고유한 정렬된 순열(distinct sorted permutations)을 모두 출력해야 합니다. 이 문제의 핵심 조건은 문자열에 동일한 문자가 두 번 이상 포함될 수 있다는 점입니다. 또한 입력으로 주어지는 문자열은 이미 사전순으로 정렬된 상태라고 가정합니다.

개념을 더 잘 이해하기 위해 예제를 살펴보겠습니다.

입력 : ABD
출력 : ABD, ADB, BAD, BDA, DAB, DBA

입력 : RSTU
출력 : RSTU, RSUT, RTSU, RTUS, RUST, RUTS, SRTU, SRUT, STRU, STUR, SURT, SUTR, TRSU, TRUS, TSRU, TSUR, TURS, TUSR, URST, URTS, USRT, USTR, UTRS, UTSR

순열(Permutation)이란?

순열(permutation)은 집합의 모든 원소를 특정 순서나 규칙에 따라 재배열하는 것을 의미합니다. 여기서 집합은 정렬되어 있을 수도 있고, 그렇지 않을 수도 있습니다.

문제 해결 로직

문제를 충분히 이해했으니, 이제 해결을 위한 로직을 세워 보겠습니다.

순열과 관련된 잘 알려진 수학 공식이 있습니다. 서로 중복 없는 n개의 문자로 구성된 문자열에서 만들 수 있는 문자열의 총 개수는 n!입니다. 반면 문자열에 중복 문자가 포함되어 있다면, 생성 가능한 문자열의 총 개수는 n! / i!로 계산됩니다. 여기서 i!는 각 중복 문자가 반복되는 횟수의 팩토리얼입니다.

예를 들어 문자열 STURS의 경우, 'S'가 2번 등장하므로 생성할 수 있는 문자열의 총 개수는 5! / 2! = 60개입니다.

생성될 문자열의 개수를 알았으니, 이제 실제로 문자열들을 만들어야 합니다. 먼저 문자열이 정렬되어 있지 않다면 정렬합니다(입력 문자열은 이미 정렬되어 있다고 가정). 그다음 문자열의 첫 번째 문자를 고정한 뒤 나머지 문자들의 순열을 구하고, 이 과정을 재귀적으로 반복합니다. 이렇게 하면 필요한 모든 순열을 정렬된 형태로 얻을 수 있습니다.

동작 예시

입력 − RST

로직 −

이 문자열로부터 총 3! = 6개의 순열을 만들 수 있습니다.

  • 'R'을 고정하고 나머지 S, T의 순열을 구하면 → RST, RTS
  • 'S'를 고정하면 → SRT, STR
  • 'T'를 고정하면 → TRS, TSR

따라서 최종 출력은 RST, RTS, SRT, STR, TRS, TSR이 되며, 모두 정렬된 순서로 나타납니다.

C++ 구현 코드

이제 이 문제를 해결하는 프로그램을 작성해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

// 중복 스왑 방지: start ~ curr-1 범위에 str[curr]와 같은 문자가 이미 있으면 false 반환
bool swaper(char str[], int start, int curr){
    for (int i = start; i < curr; i++)
        if (str[i] == str[curr])
            return 0;
    return 1;
}

void printPermutations(char str[], int index, int n){
    if (index >= n) {
        cout<<str<<"\t";
        return;
    }
    for (int i = index; i < n; i++) {
        bool check = swaper(str, index, i);
        if (check) {
            swap(str[index], str[i]);
            printPermutations(str, index + 1, n);
            swap(str[index], str[i]); // 백트래킹: 원래 상태로 복원
        }
    }
}

int main(){
    char str[] = "AABC";
    int n = strlen(str);
    cout<<"The string is : "<<str<<endl;
    cout<<"The distinct sorted permutations are : \t";
    printPermutations(str, 0, n);
    return 0;
}

실행 결과

The string is : AABC
The distinct sorted permutations are : AABC AACB
     ABAC ABCA ACBA ACAB BAAC
     BACA BCAA CABA CAAB CBAA

코드 설명

이 코드의 핵심은 swaper() 함수입니다. 문자를 교환(swap)하기 전에 현재 위치 앞쪽 범위에 동일한 문자가 이미 존재하는지 검사하여, 중복된 순열이 출력되는 것을 사전에 차단합니다. 또한 재귀 호출이 끝난 뒤 swap을 되돌리는 백트래킹(backtracking) 기법으로 문자열을 원래 상태에 복원함으로써, 가능한 모든 순열을 빠짐없이 탐색할 수 있습니다. 입력 문자열이 정렬된 상태이기 때문에 결과 역시 자동으로 사전순에 가까운 순서로 출력됩니다.