1759 암호 만들기

암호 만들기 (1759)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1759 암호 만들기

int L, C;

vector<char> letters;
bool used[15];
string collection = "aeiou";
// 재귀 : "위치"에 어느 알파벳이 들어가는지 기준으로
void solve(int count, int index){
	// 기저사례 : 길이가 L 과 같아지면
	if(count == L){
		string tmp;
		for(int i = 0; i < C; i++){
			// 추정 pw 구현
			if(used[i]){
				tmp.push_back(letters[i]);
			}
		}
		// 기저사례 : 모음이 하나 이상, 자음이 2개 이상이라면
		int collectionCount = 0;
		for(int i = 0; i < 5; i++){
			for(int j = 0; j < L; j++){
				if(collection[i] == tmp[j])
					collectionCount++;
			}
		}
		
		if(collectionCount >= 1 && L - collectionCount >= 2){
			cout << tmp << '\n';
		}
	}
	
	for(int i = index; i < C; i++){
		used[i] = true;
		solve(count + 1, i + 1);
		used[i] = false;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> L >> C;
	
	for(int i = 0; i < C; i++){
		char tmp;
		cin >> tmp;
		letters.push_back(tmp);
	}
	sort(letters.begin(), letters.end());
	fill_n(used, 15, false);
	
	solve(0, 0);
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

풀이

1. 브루트 포스가 가능할까?

- '오름차순' 이라는 조건이 붙었기 때문에 경우의 수가 많이 줄어들어 가능하다고 생각했다. 오름차순으로 정렬하여 모든 경우의 수를 따져보면 15개의 알파벳은 절대 1억의 경우의 수를 만들 수 없다.

2. 문제의 조건을 기저사례로

- 오름차순 : input 을 오름차순으로 아예 정렬해버림

- 길이가 L : 기저사례에 추가

- 최소 1개의 모음, 최소 2개의 자음을 만족해야함 : 2번째 기저사례를 통과한다면, 검사한다.

3. 각 위치에 사용할 알파벳을 정하는 것으로 ? 알파벳을 사용하느냐 마느냐로 ?

- 오름차순으로 미리 배열을 정렬해두었기에 둘 다 비슷하다고 생각하였다. 다만, 쓴 문자를 저장하는 것을 push_back 하여 한다면 계산 복잡도가 증가하기에, 사용했다는 정보만을 used 배열에 저장해두었다가 마지막에만 push_back 하였다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 처음으로, 깔끔하게 구현했고, 한번에 맞았다. 노트에 생각을 정리하여 알고리즘의 전체적인 흐름과 기저사례를 설정 하고 풀이에 돌입하는 것이 더욱 중요하다는 것을 느꼈다.

- 재귀를 조금 깨우친 느낌이다. 하지만, 메모이제이션에 대해서 기억이 흐릿해지는 것 같아 아쉽다. 종만북에 대한 아쉬움.. 기본을 더 쌓고 나중에 해보면 될 것이다.