[Baekjoon][C++] 1759번 암호 만들기 문제설명 및 코드

▷ 문제설명

1759번: 암호 만들기

주어진 암호를 만들 수 있는 문자열 L 개에서 C개를 골라서(순열) 오름차순으로 출력하는 문제.

단, 암호는 모음의 개수는 1개 이상이고 자음의 개수는 2개 이상인 문자로 이루어져 있다.

 

▷ 문제풀이

순열문제 이므로 재귀함수를 이용한 DFS 방법으로 풀이할 수 있습니다.

 

[ 변수 설명 ]

vector<char> alpha; 알파벳의 개수만큼 쉽게 입력받기 위해 vector 자료구조 사용(동적할당)

string answer_arr = ""; 정답 출력을 쉽게 하기 위해 string 자료구조를 사용하여 한번에 출력했습니다.

 

[ 알고리즘 설명 ]

문제에서 주어진 알파벳의 길이 내에서 선택할 수 있는 길이까지 재귀함수로 탐색합니다.

재귀함수는 두가지 경우의 수로 나눠서 탐색합니다.

 

① 현재 인덱스의 알파벳을 선택하는 경우

② 현재 인덱스의 알파벳을 선택하지 않는 경우

 

즉, 첫번째 문자부터 선택할 수 있는 알파벳의 개수까지 선택하고(1번 경우)

재귀함수를 반환해서는 2번의 경우로 탐색합니다.

 

이 때, 탐색할 때마다 선택한 문제의 조건이 맞는지 확인하고 맞다면 그 그 결과를 출력합니다.

 

 

▷ 시간복잡도

위 설명에서 적은 2가지 경우의 수를 알파벳의 길이만큼 재귀함수로 반복하므로

O(2^N)의 시간복잡도를 갖는다. 

 

▷ 코드

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

void findPassword(int, string, vector<char>&, int);
bool countMoumJaum(string&);

int main() {
	int length, count;
	vector<char> alpha;
	string answer_arr = "";

	cin >> length >> count;

	for (int i = 0; i < count; i++) {
		char x;
		cin >> x;
		alpha.push_back(x); // a t c i s w
	}
	sort(alpha.begin(), alpha.end()); // a c i s t w
	findPassword(length, answer_arr, alpha, 0);
}

void findPassword(int length, string answer, vector<char> &alpha, int alpha_index) {
	if (answer.length() == length && countMoumJaum(answer)) {
		cout << answer << "\n";
		return;
	}
	if (alpha_index >= alpha.size()) return;

	findPassword(length, answer + alpha[alpha_index], alpha, alpha_index+1);
	findPassword(length, answer, alpha, alpha_index+1);
}

bool countMoumJaum(string &answer) {
	int moum_count = 0, jaum_count = 0;

	for (char x : answer) {
		(x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') ? moum_count += 1 : jaum_count += 1;
	}
	return moum_count >= 1 && jaum_count >= 2;
}