백준 1759. 암호 만들기

알고리즘 기초 문제 중 브루트포스-재귀 문제(530)

암호만들기

1. 간단 설명

C개의 문자 중에서 L개를 뽑아 비밀번호를 만든다

생성한 비밀번호는 최소 한개의 모음과, 최소 두개의 자음으로 구성되어 있어야한다고 함

또한, 알파벳이 증가하는 순서로 배열되어있다고 한다

즉, abc는 가능하지만 bac처럼 순서가 거꾸로 되는건 안된다

2. 예시

abc -> 모음이 없어서 탈락

bac -> a가 b보다 빠르기 때문에 탈락

4 6
a t c i s w

atci -> 모음2개, 자음2개 OK atcs -> 모음2개, 자음2개 OK … tcsw -> 자음만 4개 탈락

이런식으로 비밀번호를 생성한 뒤 검증한다

3. 알고리즘

자음 모음을 분리해서 받아, 조합할때 하나씩 넣는 방법도 있겠지만

간단하게 하나의 벡터에 받은 다음에 나중에 검증하는식으로 구현했다

1. L과 C를 입력받는다
2. C개의 알파벳을 입력받는다
3. 입력받은 알파벳들을 정렬한다
4. 이 알파벳들로 조합을 생성해본다
	4-1. 가지치기 조건 : 글자 수가 L개라면, 검증한다
		4-1-1. 자음 2개, 모음1개라면 가능, 아니라면 불가능하므로 출력하지 않는다
	4-2. 벡터의 알파벳이 사용되었는지 체크한다
		4-2-1. 만약 사용되었다면 패스한다
		4-2-2. 사용되지 않았다면, 이 알파벳을 넣는다
		4-2-3. 재귀함수를 다시 호출한다

필요 변수들

• int L, C (3 ≤ L ≤ C ≤ 15)
• 문자를 저장할 벡터 vector<char> ch
• 자음 모음 개수를 체크할 변수 int consonant, vowel

4. 소스코드

직접 구현한 조합 버전

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int L, C;
vector<char> v;

bool check(string str) {
	int consonant = 0;
	int vowel = 0;

	for (char ch : str) {

		if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
			vowel++;
		else
			consonant++;
	}
	if (consonant >= 2 && vowel >= 1) {
		return true;
	}
	else {
		return false;
	}
}

void recursion(string str, int level, int start) {
	if (str.size() == L) {
		if (check(str)) {
			cout << str << '\n';
		}
		return;
	}

	for (int i = start; i < v.size(); i++) {
		str += v[i];

		recursion(str, level + 1, i+1); // 현재 알파벳 다음 알파벳부터 보므로, 중복체크 필요없음

		str.pop_back();
	}
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> L >> C;
	v.resize(C);

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

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

	recursion("", 0, 0);

	return 0;
}

• next_permutation을 이용한 조합

#include <bits/stdc++.h>

using namespace std;

bool check(string str) {
	int consonant = 0;
	int vowel = 0;

	for (char ch : str) {
		
		if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
			vowel++;
		else
			consonant++;
	}
	if (consonant >= 2 && vowel >= 1) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	int L, C;
	vector<char> v;
	cin >> L >> C;
	v.resize(C);

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

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

	vector<int> idx; // 조합을 위한 벡터
	for (int i = 0; i < L; i++) {
		idx.push_back(0);
	}
	for (int i = 0; i < C-L; i++) {
		idx.push_back(1);
	}

	do {
		string str = "";
		for (int i = 0; i < idx.size(); i++) {
			if (idx[i] == 0) {
				str += v[i];
			}
		}
		if (check(str)) {
			cout << str << '\n';
		}
	} while (next_permutation(idx.begin(), idx.end()));

	return 0;
}

2년전에 알고리즘 공부하다가 나중으로 미뤘던 문제였는데

오랜만에 다시 풀어보니 쉽게 풀렸다

역시 알고리즘은 꾸준히 공부하는게 답인듯 싶다