백준 1759번 암호 만들기

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

1759번: 암호 만들기

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

이 문제는 재귀 호출로 풀었습니다!

문자의 수가 15개를 넘지 않기 때문에 C개의 문자들중 L개의 알파벳으로 구성되는 암호를 모두 구하고, 

이 암호가 조건에 만족하는지 구하면 된다.

 

첫번째로, 사전식으로 암호를 출력해야하기 때문에 먼저 C개의 문자를 정렬하고, 첫 글자부터 재귀호출을 이용하면 출력 조건을 만족할 수 있다.

 

그렇다면 재귀호출을 어떻게 설계해야 할까?

우선, 나는 재귀함수의 인자로 string(만들어나가는 암호), a(모음 개수), b(자음 개수) 그리고 입력으로 받은 알파벳을 돌면서 사용할지 말지 결정하는 알파벳 인덱스 i 를 넣었다.

 

이후, 재귀함수 코드 내에서 string 의 길이가 L과 같을 때 a,b의 개수를 확인해서 맞으면 출력을 했고,

만약 i가 알파벳 총 개수를 넘어가면 바로 return 시켰다.

 

그 다음 string을 만들어나가는 부분이 가장 중요한데, 재귀함수 내에서 함수를 호출시킬 때

그 다음 index의 알파벳을 넣을지 말지 결정하지 않고 둘 다 호출을 시켜버렸다.

• pas(alpha, password + alpha[i],a+1,b, i + 1);
• pas(alpha, password + alpha[i],a,b+1, i + 1);
• pas(alpha, password,a,b, i + 1);

이런식으로 자음일 때와 모음일 때 + 그냥 index를 +1 시켜주는 함수로 구성을 하면,

모든 암호를 만들어 확인해볼 수 있다.

 

소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int l, c;
//a: 모음 수, b: 자음 수, i : 사용할지 말지 결정해야하는 알파벳 인덱스
void pas(vector<char>& alpha, string password, int a, int b, int i) {
    if (password.length() == l) {
        if (a >= 1 && b>= 2) {
            cout << password << "\n";
        }
        return;
    }
    if (i == alpha.size()) return;
    if (alpha[i] == 'a' || alpha[i] == 'e' || alpha[i] == 'i' || alpha[i] == 'o' || alpha[i] == 'u') {
        pas(alpha, password + alpha[i],a+1,b, i + 1);
    }
    else pas(alpha, password + alpha[i],a,b+1, i + 1);
    //패스하고 다음으로 넘어가는 경우
    pas(alpha, password,a,b, i + 1);
}
int main() {
    scanf("%d%d", &l, &c);
    vector<char> alpha(c);
    for (int i = 0; i < c; i++) {
        cin >> alpha[i];
    }
    sort(alpha.begin(), alpha.end());
    pas(alpha, "", 0, 0,0);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~