C++ / 백준 / 1759 / 암호 만들기

문제

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

1759번: 암호 만들기

문제풀이

DFS가 아닌 비트마스크를 이용하여 문제를 풀었다.

글자를 모두 입력받고 정렬한다.

모든 경우의 수를 돌면서 해당 글자가 자음인지, 모음인지를 확인하고, 조건들을 만족했을 때 set인 answer에 insert 했다.

반복이 종료되면 set의 원소를 모두 출력한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string word = "";
	string code = "";
	int L(0), C(0);
	int consonant(0), vowel(0);
	int idx(0), idx2(0);
	set<string>answer;
	set<string>::iterator it;
	cin >> L >> C;
	char character = ' ';
	for (idx = 0; idx < C; ++idx) {
		cin >> character;
		word += character;
	}

	sort(word.begin(), word.end());
	
	for (idx = 1; idx < (1 << C); ++idx) {
		consonant = 0;
		vowel = 0;
		code = "";
		for (idx2 = 0; idx2 < C; ++idx2) {
			if (idx & (1 << idx2)) {
				if (word[idx2] == 'a' || word[idx2] == 'e' || word[idx2] == 'i' || word[idx2] == 'o' || word[idx2] == 'u')
					++vowel;
				else ++consonant;
				code += word[idx2];
			}
		}
		if (vowel >= 1 && consonant >= 2 && vowel + consonant == L)
			answer.insert(code);
	}

	for (it = answer.begin(); it != answer.end(); ++it)
		cout << *it << '\n';
}