[BOJ 백준] 암호 만들기(1759) C++

링크 : https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

문제 설명 : 

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

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

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

출력 : 

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

 

예제 입력 : 

4 6
a t c i s w

 

예제 출력 : 

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 

접근법 : 

1) 어떻게 풀 것인가?

암호를 풀어야하는데 길이는 최대 15이고 ① 알파벳은 무조건 1개씩만 사용하며, ② 오름차순으로 암호를 사용한다.

③ 모음 1개 이상, 자음 2개 이상을 반드시 사용해야한다.

 

위의 조건들을 잘 보면

① 알파벳은 무조건 1개씩만 사용 → 제곱의 경우가 아닌 순열으로 경우의 수를 낮춰줌

② 오름차순으로 암호를 사용한다. → 순열이 아닌 조합으로 경우의 수를 낮춰줌 (순서가 전혀 상관없으므로)

 

여기까지만 해도 조합으로 문제 해결이 가능하다. 즉, 단순 DFS 또는 백트래킹으로 문제를 풀 경우 가능하다.

15길이의 조합의 최대 값은 15C7의 6,435 가지 경우의 수이므로 넉넉하다.

 

여기에 조건을 조금 더 활용한다면,

③ 모음 1개 이상, 자음 2개 이상을 반드시 사용해야한다.

→ 모음 없이 자음만 있는 경우 답이 아님

    Ex> a c e d i j k l p q s t v w x 라는 경우가 주어지고 암호 길이가 7일때

      ③ 조건으로 인해 a, i 가 모두 제외된 경우는 확인하지 않아도 된다. 즉, 13Combination7 의 경우의 수가 절약된다.

      즉, 전체 15Combination7 = 6,435 가지 경우의 수 중 1,716 경우의 수를 절약 가능 (약 27% 절감)

 

참고 : 무차별 대입 공격 (브루트포스)

https://ko.wikipedia.org/wiki/%EB%AC%B4%EC%B0%A8%EB%B3%84_%EB%8C%80%EC%9E%85_%EA%B3%B5%EA%B2%A9

무차별 대입 공격 - 위키백과, 우리 모두의 백과사전

 

2) 시간복잡도

앞서 분석을 했는데 최악의 경우도 6,435가지이므로 C나 C++의 경우엔 왠만하면 0ms가 가능할듯.

(Java 기준 -  108ms)

 

3) 공간복잡도

위의 경우의 수를 계산해서 넉넉하게 10,000개의 정답 String 배열을 선언해줘도 될듯하고 

사실 정답 배열은 필요없이 순서대로 바로 출력해도 무방하다.

굳이 계산을 해보자면 10,000 개에 최대 15개의 char라면

150,000 * 1Bytes = 146Kbytes 로 아주 작다.

그래도 Java를 쓴다면 ArrayList로 동적배열을 하는  것이 난이도가 올라가면 활용도가 더 많으므로 추천.

 

4) 풀면서 놓쳤던점

특별히 없음. DFS 중에서 난이도 쉬운 편

 

5) 이 문제를 통해 얻어갈 것

DFS, 백트래킹 기본 구현.

조건이 추가될때 어떻게 구현할 것인지 (모음, 자음 제한조건)

백준 1062 가르침 문제랑 같이 풀기 좋다.

문제 : https://www.acmicpc.net/problem/1062 

1062번: 가르침

풀이 : https://subbak2.tistory.com/5

[BOJ 백준] 가르침(1062) Java

 

C++ 코드 : 

// 암호 만들기 1759 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

#define MAX (15+2)

using namespace std;

int L, C;
int ans;						// ans : 정답

char inputString[MAX];

vector<string> answerList;

bool charCompare(const char &a, const char &b) {
	if (a < b) return true;
	return false;
}

void input();
void dfs(int id, int moeum, int cnt, string str);
void output();


int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	input();

	// 2. 정렬한다.
	sort(inputString, inputString+C, charCompare);

	// 3. dfs를 수행한다
	dfs(0, 0, 0, string(""));

	// 4. 정답을 출력한다.
	output();

	return 0;
}

void input() {
	scanf("%d %d", &L, &C);
	// cin >> L>> C;
	for (int i = 0; i < C; i++) {
		scanf(" %c", &inputString[i]);
	}
}

// id : 현재 위치, moeum : 모음 개수, cnt : 만들 배열 길이
void dfs(int id, int moeum, int cnt, string str) {
	// 글자수 다 채움 / 모음개수 1개 이상 / 자음 2개 이상
	if (cnt == L && moeum >= 1 && cnt - moeum >= 2) {
		answerList.push_back(str);
		return;
	}

	// 배열을 다 채우지 못하고 종료
	if (id == C) return;

	// 모음인 경우
	if (inputString[id] == 'a' || inputString[id] == 'e'
		|| inputString[id] == 'i' || inputString[id] == 'o'
		|| inputString[id] == 'u') {
		
		dfs(id + 1, moeum + 1, cnt + 1, str + inputString[id]);
	}

	// 자음인 경우
	else {
		dfs(id + 1, moeum, cnt + 1, str + inputString[id]);
	}
	// 문자를 선택 안 할 경우
	dfs(id + 1, moeum, cnt, str);
}

void output() {
	for (int i = 0; i < answerList.size(); i++) {
		printf("%s\n", answerList[i].c_str());
	}
}
#endif