[백준 1342] 행운의 문자열

작성일 | In |

문제 링크

https://www.acmicpc.net/problem/1342

풀이

$S$의 길이가 매우 작기 때문에 $S$를 재배치해서 만들 수 있는 모든 문자열을 확인할 수 있습니다. $len(S)!$의 모든 문자열을 본다면 구한 정답은 중복을 처리하지 않은 상태라서 문제에서 요구하는 답과는 다릅니다. 문자열의 중복이 일어나기 위해서는 같은 알파벳끼리 자리를 바꾸는 경우 뿐이고 알파벳마다 경우의 수는 $count(a)!$이므로 이 경우의 수를 중복이 포함된 정답에서 나눠준다면 중복을 제외한 문자열의 개수를 구할 수 있습니다. 모든 문자열을 보고 각 문자열이 행운 문자열인지 판별하기에 시간복잡도는 $O(S! ⋅ S)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, ans, cnt[26], fac[11];
string s;
set<string> st;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> s;
    n = s.size();
    vector<int> p(n);
    for(int i=0;i<n;i++) p[i] = i;
    do{
        int flag = 1;
        for(int i=1;i<n;i++) if(s[p[i-1]] == s[p[i]]) flag = 0;
        if(flag) ans++;
    }while(next_permutation(p.begin(), p.end()));

    fac[0] = 1;
    for(int i=1;i<=10;i++) fac[i] = fac[i-1] * i;

    for(int i=0;i<n;i++) cnt[s[i]-'a']++;
    for(int i=0;i<26;i++) ans /= fac[cnt[i]];

    cout << ans;
}