[C++] 백준 1759번 - 암호 만들기

오랜만에 풀어본 Brute Force 문제

C++에는 순열을 쉽게 만들 수 있는 algorithm 헤더에 next_permutation(혹은 prev_permutation) 메서드가 존재한다.

그러나 우리가 풀고자 하는 것은 조합을 만들어야 하는 것이기 때문에 1의 개수를 L개 만큼, 그리고 0의 개수를 C-L개 만큼 넣어준다음에 해당 벡터에 1이 나온다면 출력하는 식으로 조합을 만들 수 있다. 

그렇게 Possible한 String을 만들었다면 vowel과 noun의 개수가 맞는지 체크하고 출력해주면 되는 문제이다. 

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int l, c;

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> l >> c;
	vector<string> v(c);
	for (int i = 0; i < c; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	
	vector<int> temp_v;
	for (int i = 0; i < l; i++) {
		temp_v.push_back(1);
	}
	for (int i = 0; i < v.size() - l; i++) {
		temp_v.push_back(0);
	}
	sort(temp_v.begin(), temp_v.end());
	vector<string> ans;
	string pwd = "";
	do {
		for (int i = 0; i < temp_v.size(); i++) {
			if (temp_v[i] == 1) {
				pwd += v[i];
			}
		}
		ans.push_back(pwd);
		pwd = "";
	} while (next_permutation(temp_v.begin(), temp_v.end()));

	for (int i = ans.size() - 1; i >= 0; i--) {
		int vowel = 0, noun = 0;
		for (int j = 0; j < l; j++) {
			if (ans[i][j] == 'a' || ans[i][j] == 'e' || ans[i][j] == 'i' || ans[i][j] == 'o' || ans[i][j] == 'u') vowel++;
			else noun++;
		}
		if (vowel >= 1 && noun >= 2)
			cout << ans[i] << endl;
	}

	return 0;
}