문제 요약 및 풀이
문제 상에 주어지는 문자열의 길이는 최대 10이다.
한 문자열이 행운의 문자열인지 판단하기 위해 쭉 훑는 방법은 \(O(n), (n <= 10)\) 이다.
근데, 주어진 문자열로 만들 수 있는 모든 문자열을 나이브하게 해도 \(n!\) 이고, 최대 10!인데,
이는 \(3,628,800\) 밖에 되지 않는다.
따라서 모든 문자열을 다 훑고 판단해도 \(36,288,000\) 이기에 바로 구현하면 된다.
이때 모든 문자열을 훑는 방법은 다양하지만 c++ algorithm 헤더에 있는 next_permutation을 활용하면 편하다.
(next_permutation 함수는 어떤 케이스를 돌리느냐에 따라 시간이 달라질 수 도 있다… 잘 거르고 선택하자.)
풀이 코드
next_permutation을 활용할 때는 2가지를 조심해야 한다.
- 모든 경우를 탐색하고자 한다면, 정렬을 하고 활용해야 한다.
next_permutation을 하고 나서, 바로 다음 경우의 수가 나오는 것이기에 맨 처음 경우의 수를 따로 확인을 하든지, 혹은 do-while 문을 활용하면 편하다.
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
29
30
#include <bits/stdc++.h>
using namespace std;
string s;
int ans;
bool is_lucky_string() {
char last = 0;
for(auto i: s) {
if(i == last) return false;
last = i;
}
return true;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> s;
sort(s.begin(), s.end());
do {
if(is_lucky_string()) ans++;
}
while(next_permutation(s.begin(), s.end()));
cout << ans;
}
끝