[1759번] 암호 만들기

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

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

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

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

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

[예제입력]

4 6

a t c i s w

[예제출력]

acis

acit

aciw

acst

acsw

actw

aist

aisw

aitw

astw

cist

cisw

citw

istw

[풀이를 위한 개념]

경우의 수를 모두 살펴보는 문제로 문자의 만들어진 조합을 만들어 내는 DFS 문제입니다.

문제에 나와 있듯이 사전순으로 문자를 정렬해야하고 문자를 따로따로 저장해야 합니다.

배열을 사용할 수도 있지만 C++에서는 배열보다 vector가 용이하므로 vector를 사용하겠습니다.

vector container는 C++ STL(Standard Template Library)의 용이함을 보여주는 대표적인 예라고 생각합니다.

(STL이란 유저가 더 사용하기 편하게 자료구조와 템플릿을 제공하는 라이브러리입니다. 한마디로 유저들에게 더 다양하고 유용한 장비를 제공하는거죠. 

+ vector 뿐만 아니라 이 문제에서 사용할 algorithm 함수 템플릿을 통해 문자나 숫자를 사전순으로 깔끔하게 정리하는 장비도 사용합니다.) 

vector는 배열과 다르게 자동으로 메모리를 할당합니다.

번거롭게 동적할당 배열을 사용할 필요가 없죠. 다만 크기를 정하지 않았기 때문에 데이터를 추가하거나 제거하는 일이 빈번하다면 사용하지 않는게 좋습니다. (Stack overflow와 같은 오류가 날 수 있습니다.)

vector를 이용하면 데이터 삭제와 삽입 등이 편리합니다. vector는 queue와 비슷하게 타입을 정해서 선언할 수 있습니다.

vector <int> v;

로 선언가능하고 배열처럼 v[]로 사용 가능합니다.

[풀이과정]

사전순으로 나열해야하고 사용했던 문자는 사용할 수 없습니다. 사전순으로 나열하기 때문에 사용했던 조합은 다시 사용할 수 없습니다.

그렇기 때문에 트리형태로 모든 node에 모든 알파벳을 넣어가는 과정을 생각하기 보다 사전순으로 주어진 알파벳을 뽑을 건지 뽑지 않을 건지 선택하면 답을 구할 수 있습니다.

[그림1] 알파벳을 순서대로 선택할지 선택하지 않을지 결정하면 된다.

하지만 이 과정 또한 트리형 데이터로 표현할 수 있습니다.

[그림2] 알파벳 순서대로 층별 node 마다 해당순서 알파벳을 선택할지, 선택할지 안할지를 결정하면 된다. X표시는 이미 구하고자 하는 알파벳 4개가 모두 완성됐으므로 더이상 진행하지 않는다. 

그림처럼 정리된 알파벳이 순서대로 내려가면서 알파벳을 쓰는 경우, 쓰지 않는 경우를 모두 수행시킵니다.

다만 쓰는 경우에는 알파벳이 모음일 때와 자음일 때를 나눠서 표시하고 따로 수행시킵니다.

정리하면,

1. (출력)비밀번호를 만든 경우

2. (중지)모든 알파벳을 다 방문한 경우

3. (재귀)알파벳을 사용하는 경우 - 자음

           - 모음

4. (재귀)알파벳을 사용하지 않는 경우

으로 나눠서 작성하면 됩니다. 재귀를 통해 다음으로 넘어가는 경우는 총 3가지가 됩니다.

[정답]

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
void func(int L, vector<char> &alpha, int mo, int ja, string password, int index)
//func(구하고자하는 알파벳 개수(L), 정리된 알파벳(문자들을 그대로 받아올 수 없으므로 벡터의 주소를 받아온다), 모음(mo), 자음(ja), 만들어진 비밀번호(password), 정리된 알파벳 순서의 index(index))
{
    if(password.length() == L)            //만들어진 password의 길이가 구하고자하는 비밀번호의 길이와 같으면 중지
    {
        if(mo>=1 && ja>=2)                //모음 1개 이상, 자음 2개이상 조건에 맞는지 확인
        {
            cout << password << endl;    //출력
            return;
        }
    }
 
    if(index == alpha.size()) return;    //선택판단 횟수가 주어진 알파벳 개수보다 높아지면 중지(무한루프방지)
 
    if(alpha[index] == 'a' || alpha[index] == 'e' || alpha[index] == 'i' || alpha[index] == 'o' || alpha[index] == 'u')        //알파벳 사용 + 모음일때
    {
        func(L, alpha, mo+1, ja, password+alpha[index], index+1);
    }
    else                                                                                                                    //알파벳 사용 + 자음일때
    {
        func(L, alpha, mo, ja+1, password+alpha[index], index+1);
    }
 
    func(L, alpha, mo, ja, password, index+1);                                                                                //알파벳 사용하지 않을때
 
 
 
 
 
}
 
 
int main()
{
    int l,c;
    int m;
    int j;
 
    cin >> l >> c;
 
    vector<char> a(c);
    for(int i = 0; i<c; i++)
    {
        cin >> a[i];
    }
 
    sort(a.begin(), a.end());        //사전순 정리
 
    func(l,a,m,j,"",0);
 
    return 0;
 
 
 
}

    

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다 

1. 순서가 중요하고 중복이 안된다는 점에서 알파벳 선택여부를 통해 문제를 푼다는걸 쉽게 인식하지 못했다.

순서가 중요하다면 next_permutation을 이용한 순열문제로 풀수도 있을 듯?

2. func의 매개변수인 vector<char> &alpabet 에서 &를 사용하는 것을 놓쳤다. 포인터를 통해 저장되는 배열이나 벡터, 큐를 매개변수로 받아올 때 항상 주소로 받아와야한다.