알고리즘 :: 백준 :: Bruteforce :: 1759 :: 암호 만들기

문제

문제링크
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

문제접근

조합 방법

• 후보 문자 C개 중 L개를 선택해서 모든 경우의 수를 출력하는 전형적인 조합 (combination) 문제다.
• bool 타입 또는 char 타입의 check[C] 라는 이름의 배열을 만들고 L개의 0과 C-L개의 1을 채워넣는다.
• <algorithm> 헤더의 next_permutation()함수를 이용해서 check[ ] 배열의 순열을 구한다. 이때 함수의 default comparator가 오름차순으로 설정되어있다.
• check[i] == 0일 때의 i번째 후보 문자를 비밀번호 배열에 추가하면 next_permutation()을 위한 do-while()문이 끝났을 때 비밀번호 후보가 만들어진다. 이 후보들을 출력하면 된다.

Bruteforce - 재귀 방법

• 재귀함수의 parameter로 패스워드의 인덱스를 의미하는 idx와 이번 재귀 loop에서 사용할 후보 문자의 인덱스를 의미하는startIdx 두 가지를 사용한다.
• if (idx == L)이라면 C개의 후보 문자 중 L개를 사용해서 패스워드 후보를 만들었다는 것을 의미한다.
• if (isValid())는 이렇게 만든 패스워드 후보가 주어진 조건 모음 1개, 자음 2개를 만족하는지 확인하는 것을 의미한다.
• 재귀가 훨씬 직관적이고 코드도 간단하지만, 될 수 있으면 stack overflow와 효율성을 염두해서 forwarding으로 바꿀 수 있다면 바꾸자. 특히 재귀 호출이 함수의 마지막 부분에서 발생하는 경우 아주 높은 확률로 forwarding으로 바꾸는 것이 더 효율적이다.

추가 팁

만들어진 암호의 유효성을 검사(모음 1개이상, 자음 2개이상)할 때 유용한 방법이 있습니다. 기존의 코드는 아래와 같습니다.

bool isValid() {
	int vow = 0, cons = 0; 
	for (int i = 0; i < L; ++i)
		(pw[i]=='a'||pw[i]=='e'||pw[i]=='i'||pw[i]=='o'||pw[i]=='u') ? vow++ : cons++;
	return (vow >= 1 && cons >= 2);
}

a, e, i, o, u에 대해 비트연산을 수행하면 0x208222라는 수가 나옵니다.
따라서 코드를 아래와 같이 바꿀 수 있습니다.

bool isValid() {
	int vow = 0, cons = 0;
    	for (int i = 0; i < L; ++i)
        	(0x208222 | pw[i]) ? vow++ : cons++;
        return (vow >= 1) && (cons >= 2);
}

코드

조합

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

int L, C;
char c[15], pw[15], check[15];

bool isValid() {
	int vow = 0, cons = 0; 
	for (int i = 0; i < L; ++i)
		(pw[i]=='a'||pw[i]=='e'||pw[i]=='i'||pw[i]=='o'||pw[i]=='u') ? vow++ : cons++;
	return (vow >= 1 && cons >= 2);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> L >> C;
	for (int i = 0; i < C; ++i) cin >> c[i];
	for (int i = 0; i < L; ++i) check[i] = 0;
	for (int i = L; i < C; ++i) check[i] = 1; 
	sort(c, c + C);
	
	do {
		for (int i = 0, j = 0; i < C; ++i)
			if (!check[i]) pw[j++] = c[i];
		if (isValid()) {
			for (int i = 0; i < L; ++i) cout << pw[i]; 
                        cout << '\n';
		}
	} while (next_permutation(check, check + C));
}

Bruteforce - 재귀

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

int L, C;
char str[15], pw[15];
bool isValid() {
	int vow = 0, cons = 0; 
	for (int i = 0; i < L; ++i)
		(pw[i]=='a'||pw[i]=='e'||pw[i]=='i'||pw[i]=='o'||pw[i]=='u') ? vow++ : cons++;
	return (vow >= 1 && cons >= 2);
}
void makePw(int idx, int startIdx) {
	if (idx == L && isValid()) {
		for (int i = 0; i < L; ++i) cout << pw[i];
		cout << '\n';
		return;
	}
	for (int i = startIdx; i < C; ++i) {
		pw[idx] = str[i];
		makePw(idx + 1, i + 1);
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> L >> C;
	for (int i = 0; i < C; ++i) cin >> str[i];
	sort(str, str + C);
	makePw(0, 0);
}

결과