[BOJ/백준] 1759 암호 만들기

● [문제번호 1759] 암호 만들기

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

1759번: 암호 만들기

 

● 알아야 할 것

: DFS

: 재귀

 

● 풀이 과정

: 앞서 풀었던 DFS문제와 결이 같다.

이전에는 숫자를 가지고 순열 또는 조합을 만들었다면

이번에는 문자를 가지고 조합을 만드는 과정이다.

 

● 주의 할 것

: 맨 처음 입력된 문자 배열을 오름차순으로 정렬을 해야한다.

그래야 오름차순으로 탐색하며 저장을 한다.

 

: L과 C를 어느 곳에 사용되어야 하는지 주의해서 사용한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// alphabet : C개의 문자들을 저장할 배열
// key : C개의 문자들 중에서 L개의 가능성 있는 암호들을 저장할 배열
// visited : alphabet의 문자가 key 배열에 있는 지 확인
vector<char> alphabet;
char key[16];
bool visited[16];
int L, C;

// C개의 문자들 중에서 L개의 가능성 있는 암호 모두 구하기
void program(int cnt)
{
    // key 배열에 L개의 문자가 들어있는 경우
    if(cnt == L)
    {
        // consonant : 자음
        // vowel : 모음
        int consonant = 0;
        int vowel = 0;
        
        // (조건) 모음 최소 1개 이상 / 자음 최소 2개 이상
        for(int i = 1; i <= L; i++)
        {
            if(key[i] == 'a' || key[i] == 'e' || key[i] == 'i' || key[i] == 'o' || key[i] == 'u')
                vowel++;
            else
                consonant++;
        }
        
        // 조건을 만족하는 경우 출력
        if(1 <= vowel && 2 <= consonant)
        {
            for(int i = 1; i <= L; i++)
                cout << key[i];
            cout << "\n";
        }
    }
    
    // alphabet의 문자 하나씩 순서대로 탐색
    for(int i = 1; i <= C; i++)
    {
        // 방문한 적 없고
        // 오름차순인 경우 (중복 방지)
        if(!visited[i] && key[cnt] < alphabet[i])
        {
            // 1. 방문 체크인
            // 2. key 배열에 문자 저장
            // 3. 재귀
            // 4. 방문 체크아웃
            visited[i] = true;
            key[cnt + 1] = alphabet[i];
            program(cnt + 1);
            visited[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> L >> C;
    
    // 'a'는 임시로 저장 (다른 문자 가능)
    alphabet.assign(C + 1, 'a');
    
    // C개의 문자 저장
    for(int c = 1; c <= C; c++)
        cin >> alphabet[c];
    
    // 오름차순으로 정렬
    // 그래야 오름차순으로 탐색하며 저장함
    sort(alphabet.begin(), alphabet.end());
    
    // key 배열에 문자의 갯수가 0개 이므로
    // 0부터 시작
    program(0);
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [530 - 브루트 포스 - 재귀] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/258
2	1759	암호 만들기	https://pirateturtle.tistory.com/259
3	14501	퇴사	https://pirateturtle.tistory.com/260
4	14889	스타트와 링크	https://pirateturtle.tistory.com/261
5	15661	링크와 스타트	https://pirateturtle.tistory.com/262
6	2529	부등호	https://pirateturtle.tistory.com/263
7	1248	맞춰봐	https://pirateturtle.tistory.com/264