백준 1342번 행운의 문자열 C++

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

 

백트래킹을 이용하여 위치를 재배치한 모든 문자열을 구할 수 있다.

첫 번째 예제는 abababa 라는 문자열 하나만 행운의 문자열이지만, 답을 구해보면 144가 나오는데, 그 이유는 abababa 라는 문자가 144번 중복되어서 나오기 때문이다.

이를 해결하기 위해 a의 개수 4, b의 개수 3을 팩토리얼 연산을 하고 곱해준 뒤 답에서 나눠주어야 한다.

4! = 24, 3! = 6이고 24*6 = 144이다. 처음에 구한 답이 144이고 이것을 144로 나누면 1이 나온다.

알파벳의 각각의 개수의 정보를 저장하는 데 unordered_map 자료구조를 사용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

string str;
bool visited[10] = { false };
int cnt = 0;
unordered_map<char, int> um;

int fac(int n) {
	if (n == 0) return 1;
	if (n == 1) return 1;
	return n * fac(n - 1);
}

void BT(string s) {
	if (s.length() == str.length()) {
		cnt++;
		return;
	}
	for (int i = 0; i < str.length(); i++) {
		if (visited[i]) continue;
		if (s.length() == 0) {
			visited[i] = true;
			BT(s + str[i]);
			visited[i] = false;
		}
		else {
			if (s[s.length() - 1] == str[i]) continue;
			visited[i] = true;
			BT(s + str[i]);
			visited[i] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int div = 1;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		um[str[i]]++;
	}
	for (auto a : um) {
		div *= fac(a.second);
	}
	BT("");
	cout << cnt / div;
};