/ ALGORITHM

Baekjoon 알고리즘 - 1759번 암호 만들기 c++

1759번 암호 만들기

문제 접근 법

암호는 서로 다른 l개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다. 암호는 알파벳이 증가하는 순서로 배열되어있다.

간단한 백트래킹 문제이다. 입력으로 받은 알파벳을 정렬을 하고 백트래킹으로 모든 경우의 암호를 만든다. 암호를 만들었을때 해당 자음과 모음의 개수를 확인하고 조건에 맞으면 answer 배열에 따로 저장한다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int l, c;
vector<string> word, answer;
string moeum = "aeiou";

void make_password(int idx, int cnt, string pw) {
	// 원하는 크기의 비밀번호를 생성했으면
	if (cnt == l) {
		int cnt_moeum = 0, cnt_jaeum = pw.size();
		// 자음과 모음의 개수를 확인
		for (int i = 0; i < pw.size(); i++) {
			for (int j = 0; j < moeum.size(); j++) {
				if (pw[i] == moeum[j]) {
					cnt_moeum++;
					cnt_jaeum--;
					break;
				}
			}
		}
		// 자음과 모음의 조건이 맞으면 배열에 저장
		if (cnt_moeum >= 1 && cnt_jaeum >= 2) {
			answer.push_back(pw);
		}
		return;
	}

	for (int i = idx; i < word.size(); i++) {
		make_password(i + 1, cnt + 1, pw + word[i]);
	}
}

int main() {
	cin >> l >> c;
	for (int i = 0; i < c; i++) {
		string str;
		cin >> str;
		word.push_back(str);
	}

	sort(word.begin(), word.end());

	string tmp = "";
	make_password(0, 0, tmp);

	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << endl;
}