길이가 n(n < 10)인 문자열이 주어졌을 때, 모음과 자음의 상대적인 위치를 변경하지 않으면서 문자열을 재배치할 수 있는 경우의 수를 구하는 문제입니다.
접근 방법은 매우 간단합니다. 먼저 주어진 문자열에서 모음과 자음의 개수를 각각 센 뒤, 모음끼리 배치할 수 있는 경우의 수와 자음끼리 배치할 수 있는 경우의 수를 따로 계산합니다. 그리고 이 두 값을 곱하면 전체 경우의 수를 얻을 수 있습니다.
여기서 중요한 점은 중복되는 문자가 있을 때입니다. 같은 문자가 여러 번 등장하면 단순 팩토리얼 값에 각 문자의 빈도수 팩토리얼을 나눠주어 중복을 제거해야 정확한 결과를 얻을 수 있습니다.
알고리즘
arrangeWayCount(str)
Begin define an array 'freq' to store frequency. count and place frequency of each characters in freq array. such that freq[0] will hold frequency of letter 'a', freq[1] will hold frequency of 'b' and so on. v := number of vowels, and c := number of consonants in str vArrange := factorial of v for each vowel v in [a, e, i, o, u], do vArrange := vArrange / factorial of the frequency of v done cArrange := factorial of c for each consonant con, do cArrange := cArrange / factorial of the frequency of con done return vArrange * cArrange End
알고리즘을 단계별로 정리하면 다음과 같습니다.
- 각 문자의 빈도수를 저장할 배열(freq)을 준비하고, 문자열을 순회하며 빈도수를 기록합니다.
- 모음(a, e, i, o, u)의 개수 v와 자음의 개수 c를 셉니다.
- 모음 배치 수는 v!에서 각 모음의 빈도수 팩토리얼을 나눈 값입니다.
- 자음 배치 수는 c!에서 각 자음의 빈도수 팩토리얼을 나눈 값입니다.
- 두 값을 곱한 결과가 최종 답이 됩니다.
C++ 예제 코드
#include <iostream>
using namespace std;
long long factorial(int n){
if(n == 0 || n == 1)
return 1;
return n*factorial(n-1);
}
long long arrangeWayCount(string str){
long long freq[27] = {0}; //fill frequency array to 0
int v = 0, c = 0;
for (int i = 0; i < str.length(); i++) {
freq[str[i] - 'a']++;
if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
v++;
}else
c++;
}
long long arrangeVowel;
arrangeVowel = factorial(v);
arrangeVowel /= factorial(freq[0]); // vowel a
arrangeVowel /= factorial(freq[4]); // vowel e
arrangeVowel /= factorial(freq[8]); // vowel i
arrangeVowel /= factorial(freq[14]); // vowel o
arrangeVowel /= factorial(freq[20]); // vowel u
long long arrangeConsonant;
arrangeConsonant = factorial(c);
for (int i = 0; i < 26; i++) {
if (i != 0 && i != 4 && i != 8 && i != 14 && i != 20)
arrangeConsonant /= factorial(freq[i]); //frequency of all characters except vowels
}
long long total = arrangeVowel * arrangeConsonant;
return total;
}
main() {
string str = "computer";
long long ans = arrangeWayCount(str);
cout << "가능한 배열 방법의 수: " << ans << endl;
}실행 결과
가능한 배열 방법의 수: 720
동작 원리 살펴보기
예제 문자열 "computer"에는 모음이 o, u, e로 3개, 자음이 c, m, p, t, r로 5개 있습니다. 모음끼리의 배치 수는 3! = 6가지, 자음끼리의 배치 수는 5! = 120가지이므로 전체 경우의 수는 6 × 120 = 720가지가 됩니다. 이처럼 모음과 자음의 상대적 순서를 그대로 유지하면서 각 그룹 내부에서만 순서를 바꾸는 방식으로 문제를 분해하면 효율적으로 해결할 수 있습니다.