Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 1759] 암호 만들기 본문

대학교/Algorithm

[백준 1759] 암호 만들기

SWKo 2020. 3. 22. 17:57

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. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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<stringbool> 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-100"");
    sort(result.begin(), result.end());
    for(int i = 0; i < result.size(); i++)
        cout << result[i] << '\n';
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1182] 부분수열의 합  (0) 2020.03.24
[백준 1987] 알파벳  (0) 2020.03.23
[백준 1525] 퍼즐  (0) 2020.03.20
[백준 1697] 숨바꼭질  (0) 2020.03.19
[백준 10819] 차이를 최대로  (0) 2020.03.18
Comments