C++로 문자열의 순열 개수 구하기: 중복 문자 처리까지 한 번에

문자열의 문자들은 다양한 순서로 배열할 수 있습니다. 이번 글에서는 주어진 문자열로 만들 수 있는 순열(permutation)의 개수를 계산하는 방법을 알아보겠습니다.

순열 개수의 기본 원리

예를 들어 'abc'라는 문자열은 세 개의 서로 다른 문자로 이루어져 있으므로 3! = 6가지 방법으로 배열할 수 있습니다. 일반적으로 n개의 문자로 이루어진 문자열은 n!가지의 순열을 가질 수 있습니다.

그러나 'aab'처럼 같은 문자가 여러 번 등장하는 경우에는 상황이 달라집니다. 단순히 3! = 6이라고 계산하면 실제 고유한 순열보다 많은 개수가 나오게 됩니다.

위 목록에서 (1, 6), (2, 5), (3, 4)는 각각 동일한 순열입니다. 즉, 실제 고유한 순열의 수는 3개뿐입니다. 이는 기본적으로 n!을 중복해서 등장하는 각 문자의 빈도수 팩토리얼 값들로 나눈 것과 같습니다.

문제 해결 접근 방식

이 문제를 해결하려면 다음 단계를 따르면 됩니다.

문자열에 포함된 모든 문자의 빈도수(frequency)를 계산합니다.
문자열 길이 n에 대한 팩토리얼(n!)을 구합니다.
빈도수가 1보다 큰 각 문자에 대해 해당 빈도수의 팩토리얼 값을 n!에서 나눕니다.

예제 코드

#include<iostream>
using namespace std;
long fact(long n) {
    if(n == 0 || n == 1 )
        return 1;
    return n*fact(n-1);
}
int countPermutation(string str) {
    int freq[26] = {0};
    for(int i = 0; i<str.size(); i++) {
        freq[str[i] - 'a']++; // 각 문자의 빈도수를 개별적으로 계산
    }
    int res = fact(str.size()); // 길이가 n인 문자열에 대한 n!
    for(int i = 0; i<26; i++) {
        if(freq[i] > 1)
            res /= fact(freq[i]); // n!을 (각 문자의 등장 횟수)!로 나눔
    }
    return res;
}
main(){
    string n;
    cout << "Enter a number to count number of permutations can be possible: ";
    cin >> n;
    cout << "\nThe number of permutations: " << countPermutation(n);
}

코드 설명

fact() 함수는 재귀 호출을 통해 팩토리얼을 계산합니다. 핵심 함수인 countPermutation()은 크기 26의 정수 배열을 사용해 알파벳 소문자 각각의 등장 횟수를 저장합니다. 이후 전체 길이에 대한 팩토리얼을 구한 뒤, 두 번 이상 등장하는 문자의 팩토리얼 값으로 순차적으로 나누어 중복을 제거합니다.

예를 들어 입력이 'abbc'라면 전체 순열은 4! = 24가지이지만, 'b'가 두 번 등장하므로 24 ÷ 2! = 12가 최종 결과가 됩니다.

실행 결과

Enter a number to count number of permutations can be possible: abbc
The number of permutations: 12

이 알고리즘의 시간 복잡도는 문자열 길이에 비례하는 O(n)으로 매우 효율적입니다. 다만 팩토리얼 값이 빠르게 커지므로, 문자열이 길어지는 경우 오버플로우를 방지하기 위해 long long 타입을 사용하거나 모듈러 연산을 적용하는 것이 좋습니다.