백준 1759번 암호 만들기

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

1759번: 암호 만들기

 

전형적인 순열 구하기 문제이다. dfs 백트래킹으로 검사하고 주의할 것은 자음의 수가 2개 이상이라는 것만 체크하면 된다. 그런데 난 모음의 요소를 저렇게 검사했는데 맞는지 모르겠다. 

 

시간 복잡도는 O(조합 * N) 으로 빠른시간에 해결 가능했다. N이 높지 않은 탓이다.

 

문제를 보고 바로 파악할 수 있었다. 코테에서도 이래야할탠데...

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int L, C;

bool visited[16] = { false, };
vector<string> answer_vec;
vector<char> alphabet;

string cipher;

void dfs(int idx, int cnt) {
	if (cnt == L) {
		bool flag = false;
		int au_cnt = 0;
		for (int i = 0; i < cipher.size(); i++) {
			if (cipher[i] == 'a' || cipher[i] == 'e' || cipher[i] == 'i' || cipher[i] == 'o' || cipher[i] == 'u') {
				flag = true;
				au_cnt++;
			}
		}
		if (flag && L - au_cnt > 1) {
			string answer = cipher;
			sort(answer.begin(), answer.end());
			answer_vec.push_back(answer);
		}
		return;
	}
	
	for (int i = idx; i < C; i++) {
		if (visited[i] == true) continue;
		visited[i] = true;
		cipher.push_back(alphabet[i]);
		dfs(i, cnt + 1);
		cipher.pop_back();
		visited[i] = false;
	}
}

int main() {
	cin >> L >> C;

	for (int i = 0; i < C; i++) {
		char tmp;
		cin >> tmp;
		alphabet.push_back(tmp);
	}

	dfs(0, 0);
	sort(answer_vec.begin(), answer_vec.end());
	for (auto a : answer_vec)
		cout << a << '\n';
}