백준 1759번 암호 만들기

- 문제 설명

 

암호는 L개의 알파벳 소문자들로 구성되며, 최소 한개의 모음(a,e,i,o,u)과 두개의 자음으로 구성되어 있다.

 

암호를 이루는 알파벳은 증가하는 순서로 배열되었을 것으로 추측된다.

 

암호로 사용했을 법한 문자의 종류는 C가지일 때 가능성 있는 모든 암호들을 구하여라

 

 

- 입력

 

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15)

 

다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다.

 

 

- 출력

 

사전식으로 가능한 암호를 모두 출력

 

 

* 문제 풀이의 핵심

 

 

1. 브루트포스

 

이 문제는 브루트포스 방법을 사용해 모든 경우의 수를 구한뒤 조건에 맞는 암호를 찾는 방식으로 해답을 구해야 풀 수 있는 문제입니다.

 

브루트포스 문제는 순열의 구해야 하는 수가 모든 순열을 구하는 시간복잡도가 O(N!*N) 이기 때문에, 수의 개수가 10개 이하일 때 1초인 시간제한 내에 풀 수 있다고 볼 수 있습니다.

 

이 문제는 15개 중에 7개를 뽑는 경우가 최대라고 본다면 ₁₅C₇ = 6435 개의 경우의 수가 존재하기 때문에 2초 라는 시간 제한 안에 풀 수 있는 문제 입니다.

 

* 1초 연산 : 1억번이라고 가정

 

 

2. 알고리즘 (재귀)

 

* '암호를 이루는 알파벳은 증가하는 순서로 배열되었을 것으로 추측된다.' 라는 조건을 만족하기 위해 재귀를 통한 경우의 수를 찾기 전에 알파벳들을 오름차순 정렬을 해야 한다.

 

 

1) 모든 경우의 수 찾기

 

- L : 정답 암호의 길이, alpha : 사용할 수 있는 C개의 알파벳, str : 현재 만들고 있는 암호, curIdx : alpha의 인덱스

 

<1> 정답 암호를 찾은 경우

 

- (정답 암호의 길이 == 현재 만들고 있는 암호의 크기) 라는 조건을 만족한다면 정답 암호가 될 가능성이 있으므로 str의 자음, 모음 개수를 체크합니다.

 

 

<2> 더이상 다음 조합을 만들 수 없는 경우

 

- C개의 alpha 중에서 하나를 골라 계속 다음 암호를 만들기 때문에, (curIdx >= alpha의 크기) 라는 조건을 만족한다면 더이상 다음 암호를 만들 수 없습니다.

 

 

<3> 알파벳을 사용하는 경우와 사용하지 않는 경우

 

- a c i s t w 라는 알파벳이 있을 때

 

a c i s 라는 경우는 0~3 인덱스의 알파벳을 사용하는 경우입니다.

 

a c i t 라는 경우는 0~2, 4 인덱스의 알파벳을 사용하는 경우입니다.

 

이처럼 알파벳을 curIdx 의 알파벳을 사용할지 안할지에 따라서 암호의 조합이 바뀌게 됩니다.

 

 

=> 모든 <1>, <2>, <3> 조건을 조합하면 다음과 같은 재귀식이 나오게 됩니다.

 

void password(int L, vector<char> &alpha, string str, int curIdx) {
	if (L == str.size()) {
		if (check(str)) {		// 자음, 모음 개수 검사
			cout << str << "\n";
		}
		return;
	}

	if (curIdx >= alpha.size()) return;		// curIdx : alpha 의 인덱스

	// 순서에 따라 정순, 역순
	password(L, alpha, str + alpha[curIdx], curIdx + 1);	// 알파벳을 사용하는 경우
	password(L, alpha, str, curIdx + 1);					// 사용하지 않고 건너 뛰는 경우
}

 

 

2) 암호가 조건을 만족하는지 검사하기

 

- 자음의 개수와 모음의 개수 세기

 

문제의 조건에 따르면 '암호는 ..., 최소 한개의 모음(a,e,i,o,u)과 두개의 자음으로 구성되어 있다.' 라고 하였기 때문에, 현재 만든 암호문을 순회하면서 자음과 모음 개수를 검사하면 됩니다.

 

조건에 맞는 암호문이면 true, 그렇지 않으면 false 를 리턴하도록 만들었습니다.

 

 

bool check(string str) {
	bool ret = false;

	int ja = 0;
	int mo = 0;

	int i;
	for (i = 0; i < str.size(); i++) {
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') mo += 1;
		else ja += 1;
	}

	if (ja >= 2 && mo >= 1) ret = true;
	return ret;
}

 

 

- 소스코드

 

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

using namespace std;

bool check(string str) {
	bool ret = false;

	int ja = 0;
	int mo = 0;

	int i;
	for (i = 0; i < str.size(); i++) {
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') mo += 1;
		else ja += 1;
	}

	if (ja >= 2 && mo >= 1) ret = true;
	return ret;
}

void password(int L, vector<char> &alpha, string str, int curIdx) {
	if (L == str.size()) {
		if (check(str)) {		// 자음, 모음 개수 검사
			cout << str << "\n";
		}
		return;
	}

	if (curIdx >= alpha.size()) return;		// curIdx : alpha 의 인덱스

	// 순서에 따라 정순, 역순
	password(L, alpha, str + alpha[curIdx], curIdx + 1);	// 알파벳을 사용하는 경우
	password(L, alpha, str, curIdx + 1);					// 사용하지 않고 건너 뛰는 경우
}

int main() {
	int L, C;
	cin >> L >> C;

	vector<char> alpha(C);

	int i;
	for (i = 0; i < C; i++) {
		cin >> alpha[i];
	}
	sort(alpha.begin(), alpha.end());

	password(L, alpha, "", 0);
}

 

 

 

- 문제링크 : www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요