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

<next_permutation> 모든 경우의 수 정렬

---

next_permutation 함수를 활용해서 쉽게 접근할 수 있다. 

 

next_permutation은 모든 경우의 수를 정렬하게 되는데 이때 bool 벡터를 생성하여 변화되는 문자들만 활용해서 문자열을 생성할 수 있다.

 

이때, 체크해야 할 것은 모음이 1개 이상, 자음이 2개 이상이여야 한다는 점을 주의하자. 

 

1. 알파벳 벡터 내림차순으로 정렬 

2. check 벡터 오름차순으로 정렬 

 

ex) 두 개의 문자를 비교할 때, 

 

                         e d c b a

 

(next_permutation) 0 0 0 1 1  -> a  b  

(next_permutation) 0 0 1 0 1  -> a  c  

(next_permutation) 0 0 1 1 0 ->  b  c  

...

...

...

(next_permutation) 1 1 0 0 0 -> d e

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector <string> answer;
	int l, c;
	cin >> l >> c;
	vector <char> alpa(c);
	vector <bool> check(c, false);
	for (int i = 0; i < l; i++)check[i] = true;
	sort(check.begin(), check.end());	
	for (int i = 0; i < c; i++) cin >> alpa[i]; 	
	sort(alpa.begin(), alpa.end(), greater<char>());
	do {
		string s = "";
		int cnt1 = 0; 
		int cnt2 = 0; 		
		for (int i = c - 1; i >= 0; i--) {
			if (check[i] == false)continue; 
			char c1 = alpa[i]; 
			s += c1; 
			if (c1 == 'a' || c1 == 'u' || c1 == 'i' || c1 == 'o' || c1 == 'e') {
				cnt1++; 
			}
			else cnt2++; 
		}
		if (cnt1 && cnt2 >= 2) answer.push_back(s);
	} while (next_permutation(check.begin(), check.end()));	
	sort(answer.begin(), answer.end());
	for (auto x : answer) cout << x << "\n";
}

채점 현황