[알고리즘 풀이 분석] BOJ 1759 암호 만들기

기본적인 순열 조합 알고리즘을 구현할 줄 알아야 함을 깨달은 이후 c++ STL 라이브러리를 이용한 조합 알고리즘을 연습하였고,
완전탐색 역시 비교적 자주 출제 되는 것을 대비해 브루트 포스를 이용한 BOJ 1759번을 풀어보았다.
하지만 운 좋게 여기서도 조합 알고리즘을 이용할 수 있었기에, 기록해본다!

BOJ 1759 암호 만들기

문제는 여기서 확인!

문제 목표

주어진 모음과 자음을 이용하여 조건에 맞게, 가능한 암호들을 출력!

제한 사항

• 암호는 서로 다른 L개의 알파벳 소문자들로 구성
• 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성
• 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열

나의 풀이

글을 읽으며 조합을 이용해서 모음에서 몇개, 자음에서 몇개 고르는 경우를 추출하고 모음, 자음의 조합 결과를 cross 하여 붙이면 되겠다 생각했다!
너무 단순한가 싶었지만, 애초에 완전탐색을 이용하는 문제였기에 큰 무리 없이 진행하였다.

입력되는 숫자와 문자들을 정돈하고, 모음에서 v개 추출, 자음에서 L-v개 추출하면서 (이때 v>=1 && L-v <= 2 임을 확인하는 과정이 중요하다) 조합 알고리즘을 이용해 사용될 모음, 자음들을 배열로 반환 받는다.

이후 반환된 두 배열을 이중 포문을 이용하여 하나의 암호로 붙이고 이를 사전순으로 정렬하여 정답 배열 answer에 삽입한다

나의 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// BOJ 1759 암호 만들기, 브루트포스 이용
using namespace std;

vector<string> getCombination(vector<string> characters, int r) {
    int len = characters.size();

    vector<string> answer;

    vector<bool> check(len - r, false);
    check.insert(check.end(), r, true);

    do {
        string temp = "";
        for (int j = 0; j < len; j++) {
            if (check[j]) {
                temp += characters[j];
            }
        }
        answer.push_back(temp);
    } while (next_permutation(check.begin(), check.end()));

    return answer;
}

int main() {
    int L, C;
    cin>>L>>C;

    vector<string> answer;
    vector<string> vowel;
    vector<string> consonant;

    string ch;
    for (int i = 0; i < C ; ++i) {
        cin>>ch;
        if(ch=="a" || ch=="e" || ch=="i" || ch=="u" || ch=="o"){
            vowel.push_back(ch);
        }else{
            consonant.push_back(ch);
        }
    }

    vector<string> usedV;
    vector<string> usedC;

    for (int v = 1; v <=vowel.size() ; ++v) {
        int c = L-v;

        if (c>=2 && c<=consonant.size()){
            usedV = getCombination(vowel, v);
            usedC = getCombination(consonant, c);
        }else { // @ break 는 틀림! 
            continue;
        }

        for (int i = 0; i < usedV.size() ; ++i) {
            for (int j = 0; j < usedC.size(); ++j) {
                string ans = usedV[i]+usedC[j];

                sort(ans.begin(), ans.end());
                answer.push_back(ans);
            }
        }
    }

    sort(answer.begin(), answer.end());

    for (int i = 0; i < answer.size(); ++i) {
        if (i < answer.size()-1){
            cout<<answer[i]<<'\n';
        }else{
            cout<<answer[i];
        }
    }

    return 0;
}

기억할만한 사항

• < algorithm > 헤더의 정렬 함수 sort()를 vector 에만 사용해 보았는데, string 자체에도 사용이 가능하였다!

sort(str.begin(), str.end()); // 사전순 정렬~ 무야호~~

• 처음에 작성한 코드는 채점 결과 틀렸다고 나왔는데, @ 표시를 해 놓은 곳에서 break 대신 continue 를 사용하니 통과 되었다!

(모음에서 v 개를 뽑고, 자음에서 L-v 개를 뽑으려 할 때 L-v 가 2보다 크거나 같고 전체 자음 수보다는 작거나 같아야 하는 조건을 만족하지 못할 때)
사실 이부분은 이유를 잘 모르겠다,,ㅠㅠ
모음의 갯수를 기준으로 늘려가면서 체크하는데, 반례부분이 있으면 찾을 수 있을까 싶은데,, 일단 이부분은 좀 더 고민을 해보고 발견하는 부분이 있으면 다시 추가로 기록하겠다..!