[백준] 1342 행운의 문자열

✔️ 문제 링크

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

1342번: 행운의 문자열

---

✔️ 문제 이해

◾ 주어진 문자열을 재배치해서 행운의 문자열을 몇 개 만들 수 있는지 알아내야한다.

◾ 행운의 문자열이란 인접해 있는 모든 문자가 같지 않은 문자열이다.

---

✔️ 설계

◾ c++의 next_permuation을 사용하면 매우 쉽게 풀리는 문제이다.

◾ next_permutation은 순열을 만들때 중복을 제거해주기 때문에 중복관련해서 따로 구현하지 않아도 됐다.

◾ 시간복잡도 : 순열을 구하는 경우의수 * 인접한 문자가 중복인지 검사하는 횟수

◾ 최악의 경우 10! * 10 (36,288,000)이므로 제한된 시간내에 가능했다. 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

int main() {
	string s;
	int ret = 0;
	cin >> s;

	// 모든 순열을 구하기 위해 정렬해준다. 
	sort(s.begin(), s.end());

	do {
		// 인접한 문자가 같은지 체크한다.
		bool flag = false;
		for (int i = 0; i < s.size() - 1; i++) {
			if (s[i] == s[i + 1]) {
				flag = true;
				break;
			}
		}
		if (flag) continue;
		ret++;

	} while (next_permutation(s.begin(), s.end()));

	cout << ret;
}

---

✔️ 문제 회고

◾ next_permutation을 사용하여 정말 쉽게 풀었다.

◾ next_permutation의 덕을 많이봐서 양분이 되는 공부는 아녔다.