[백준 1759] 암호 만들기

0. 제목

• 백준 1759 암호 만들기
• BOJ 1759 암호 만들기
• C++ 1759 암호 만들기

---

1. 문제

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

---

2. 풀이

• 브루트포스를 이용하여 푸는 문제이다.
• 모음과 자음을 따로 입력받고 벡터에 각각 저장한다.
• visited는 map으로 설정하였고 해당 string에 방문한적이 있으면 true, 없으면 false를 저장한다.
• 최소 한개의 모음과 최소 두개의 자음이 포함되어야 하므로 그 조건에 맞고 길이가 길이조건인 L과 같다면  해당 문자열을 사전순으로 정렬하고 visited.count(s)가 false이면 즉, 방문한적이 없으면 result에 push 해주고 return 한다.
• 만약, 요구하는 길이인 L과 길이가 같지만 자음, 모음 조건을 만족시키지 못하면 return 한다.
• 요구하는 길이인 L보다 작으면 재귀 호출을 통해 문제를 해결한다.
• password의 인자들을 보면 idx1은 모음벡터의 index, idx2는 자음벡터의 index, vCnt는 모음 갯수, cCnt는 자음 갯수, s는 현재 문자열이다.
• 재귀 함수 호출을 통해 모든 조합을 시도한다.
• 마지막으로, 모든 탐색이 끝나면 result 벡터를 사전순으로 정렬 후 출력한다.

---

3. 코드

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
 
const int MAX = 15;
 
int L, C;
char alphabet[MAX];
vector<char> vowel;
vector<char> consonant;
vector<string> result;
map<string, bool> visited;
 
void password(int idx1, int idx2, int vCnt, int cCnt, string s){
    if(s.length() == L && vCnt >= 1 && cCnt >= 2){
        sort(s.begin(), s.end());
        if(visited.count(s) == false){
            visited[s] = true;
            result.push_back(s);
        }
        return;
    }
    
    if(s.length() == L)
        return;
    
    for(int i = idx1 + 1; i < vowel.size(); i++)
        password(i, idx2, vCnt+1, cCnt, s+vowel[i]);
    for(int i = idx2 + 1; i < consonant.size(); i++)
        password(idx1, i, vCnt, cCnt+1, s+consonant[i]);
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> L >> C;
    
    for(int i = 0; i < C; i++){
        cin >> alphabet[i];
        if(alphabet[i] == 'a' || alphabet[i] == 'e' || alphabet[i] == 'i' || alphabet[i] == 'o' || alphabet[i] == 'u')
            vowel.push_back(alphabet[i]);
        else
            consonant.push_back(alphabet[i]);
    }
    
    sort(vowel.begin(), vowel.end());
    sort(consonant.begin(), consonant.end());
    
    password(-1, -1, 0, 0, "");
    sort(result.begin(), result.end());
    for(int i = 0; i < result.size(); i++)
        cout << result[i] << '\n';
    
    return 0;
}