[BOJ/C++] 백준 1759번: 암호 만들기

 

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

 

---

 

문제

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

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

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

 

 

 

 

 

입출력 예시

입력

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

 

 

출력

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

 

 

 

입출력 예시

 

 

 

---

 

풀이 

백트래킹으로 해결할 수 있는 문제이다.

 

/* 최종 코드의 25번째줄 ~ */
vec[n] = alphabets[i];
isUsed[alphabets[i]-97] = 1;
// 생략
isUsed[alphabets[i]-97] = 0;

• isUsed로 이미 사용한 문자는 다시 사용하지 않도록 체크한다.
  • 97을 빼주는 이유는 a가 아스키코드(ASCII) 97인 점을 이용하여, isUsed[0]에 알파벳 a의 사용 유무를 저장할 수 있도록 한 것이다. 
  • z로 예를 들면, z의 아스키코드가 122이므로 isUsed[122 - 97], 즉, isUsed[25]에는 알파벳 z의 사용 여부를 담고 있을 것이다.

 

/* 최종 코드의 28번쨰 줄 ~ */
if (vowels.find(vec[n]) != vowels.end()) {
    alphabets_vowels.push_back(vec[n]);
    CreatePassword(n + 1);
    alphabets_vowels.pop_back();
}
else {
// 생략

• 암호를 만들면서 사용한 모음은 alphabets_vowels에 push_back 한다.
  • L개의 암호를 다 선택한 경우, alphabets_vowels를 이용해 모음이 1개 이상 사용하였는지, 자음은 2개 이상 사용하였는지 체크하는 용도로 쓴다. -> 최종 코드 15번째 줄의 조건식

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int L, C;
bool isUsed[30];
vector<char> alphabets;
vector<char> alphabets_vowels;
vector<char> vec;
set<char> vowels = {'a', 'e', 'i', 'o', 'u'};

void CreatePassword(int n, int idx) {
    if (n == L && !alphabets_vowels.empty() && (L - alphabets_vowels.size()) >= 2) {
        for (const auto& v : vec) {
            cout << v;
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < C; i++) {
        if (isUsed[alphabets[i]-97]) continue;
        if (n != 0 && vec[n-1] >= alphabets[i]) continue;
        vec[n] = alphabets[i];
        isUsed[alphabets[i]-97] = 1;

        if (vowels.find(vec[n]) != vowels.end()) {
            alphabets_vowels.push_back(vec[n]);
            CreatePassword(n + 1, idx + 1);
            alphabets_vowels.pop_back();
        }
        else {
            CreatePassword(n + 1, idx + 1);
        }
        isUsed[alphabets[i]-97] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> L >> C;
    alphabets.resize(C, ' ');
    vec.resize(L, ' ');
    for (int i = 0; i < C; i++) {
        cin >> alphabets[i];
    }

    sort(alphabets.begin(), alphabets.end());
    CreatePassword(0, 0);
}

 

 

 

---