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

1759번: 암호 만들기

 

아주 어렵지 않고 재밌게 풀 수 있는 순열/조합 문제다.
Input으로 주어지는 알파벳 소문자를 중복 없이 조합하되 간단한 룰을 만족하는 조합을 찾아내면 된다.

 

1. 알파벳 사전 순서로 정렬
2. 1개 이상의 모음(a, e, i, o, u)과 2개 이상의 자음을 포함

 

위 규칙을 만족하면서 각 요소의 중복이 없는 조합을 만들어 모두 출력해야 한다.

이런 순열, 조합의 문제는 DFS로 구현하거나 간단히 각 언어마다 제공되는 API가 있다면 이를 이용해 어렵지 않게 풀어낼 수 있다.

 

 

---

 

 

문제의 포인트

 

순열 혹은 조합 구하기

 

순서가 의미를 가지고 중복을 허용하지 않는다는 점에서 순열이라고 할 수 있겠지만 사실 순서는 정해져 있는 것이기 때문에 일반적인 순열 문제와 같이 접근하지는 않았다.

모든 가능한 순열을 뽑고 알파벳 순서로 정렬되지 않은 결과는 제외하는 방법도 가능하겠지만 탐색 수가 훨씬 많아질 수 있기 때문에 깊이 우선 탐색 (DFS) 형태로 풀어 보았다.

 

 

1. 입력받은 문자를 알파벳 순서로 정렬
2. 정렬된 문자열에서 뽑은 위치와 결과에 넣을 위치를 기반으로 조합
3. 재귀 호출을 이용해 순서가 정해진 모든 가능한 조합 만들기
4. 한벌의 조합이 완성되면 자음, 모음 규칙 확인

 

 

위와 같은 순서로 풀이했다.

즉, 우선 주어진 문자들을 정렬시켜두고 뽑는 순서를 기억하면서 하나씩 선택해가는 방식이다.

굳이 문자 하나를 선택하고 앞서 선택한 문자와 알파벳 순서를 비교하는 과정을 거치기 싫어서 선택한 방법이다.

 

 

자음, 모음 규칙은 조합을 완성시킨 이후 확인해서 만족하면 출력하고 그렇지 않으면 넘어가는 형태로 단순하게 확인했다.

여러번 비교할 필요 없이 한벌의 조합을 한번 순회하면서 자음, 모음 수를 카운트 하는것 만으로 간단히 확인하도록 했다.

 

 

조합을 만드는 과정에서 매번 카운트를 하거나 확인하도록 하는 방식은 오히려 더 많은 비교를 필요로 할 것 같아 시도해보지 않았다.

 

 

---

 

전체 Code

#include <iostream>
#include <algorithm>

using namespace std;

int L, C;
char P[15 + 5];
char PWD[15 + 5];

int checkRule() {
	int i, cnt_cons = 0, cnt_vow = 0;

	for (i = 0; i < L; i++) {
		if (PWD[i] == 'a' || PWD[i] == 'e' || PWD[i] == 'i' || PWD[i] == 'o' || PWD[i] == 'u')
			cnt_cons++;
		else
			cnt_vow++;
	}
	if (cnt_cons >= 1 && cnt_vow >= 2)
		return 1;
	else
		return 0;
}

void DFS(int pos, int sel) {
	int i;

	if (pos >= L) {
		if (checkRule()) {
			cout << PWD << "\n";
		}
		return;
	}

	for (i = sel; i < C; i++) {
		PWD[pos] = P[i];
		DFS(pos + 1, i + 1);
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i;

	cin >> L >> C;

	for (i = 0; i < C; i++) {
		cin >> P[i];
	}

	sort(P, P+C);
	DFS(0, 0);

	return 0;
}