JArchive 프로그래밍 일기

문제

암호 만들기 백준 1759번

리뷰

완전탐색 문제다.

주어진 C개의 문자 중에서 L개만 선택해서 만들 수 있는 암호의 개수를 센다.

암호 문자열의 조건은 자음이 2개 이상, 모음이 1개 이상이면 답이 된다.

1. 암호를 전부 만들어 본다. --> 함수 bf()
2. L개의 문자를 고른 순간, 자음/모음 개수 조건을 충족하면 출력해준다. --> 함수 check()

L개를 다 고를 때 까지 주어진 문자들을 순회하며 (idx 변수 ) string st 에 이어 붙여본다.

string st 의 길이가 L개가 되는 순간, 자음/모음 개수 조건을 확인한다.

idx 위치의 문자를 선택 한다/안한다로 재귀 호출한다.

void bf(string st, int idx){

    if(L == st.length()){ // L 개 다 고름  

        if(check(st)){ // 자음 모음 개수 충족 여부 확인  
            cout << st << '\n';
        }
        return;
    }

    if(alpha.size() <= idx) return; // 끝 

    bf(st + alpha[idx], idx+1); // idx 문자를 선택해서 st에 이어붙인다.  

    bf(st, idx+1);  // 선택안하고 지나간다. 

}

자음/모음 조건을 확인하는 함수다.

vector STL이 제공하는 find()의 기능을 활용했다.

momo 에서 x가 존재하면 x의 인덱스를 반환하고, 없으면 end()를 반환한다.

vector<char> momo{'a', 'e', 'i', 'o', 'u'};

bool check(string &pw){ // 자음 모음 개수 세기 

    int ja = 0, mo = 0;    

    for(char x : pw){

        if( find(momo.begin(), momo.end(), x) != momo.end() ){
            mo++;
        }else{
            ja++;
        }
    }

    return (ja >= 2 && mo >= 1); 
}

코드

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

int L, C;
vector<char> alpha; // 주어진 문자 
vector<char> momo{'a', 'e', 'i', 'o', 'u'};

bool check(string &pw){ // 자음 모음 개수 세기 

    int ja = 0, mo = 0;    

    for(char x : pw){

        if( find(momo.begin(), momo.end(), x) != momo.end() ){
            mo++;
        }else{
            ja++;
        }
    }

    return (ja >= 2 && mo >= 1);
}


void bf(string st, int idx){

    if(L == st.length()){ // L 개 다 고름  

        if(check(st)){ // 자음 모음 개수 충족 여부 확인  
            cout << st << '\n';
        }
        return;
    }

    if(alpha.size() <= idx) return;

    // 선택 
    bf(st + alpha[idx], idx+1);
    // 선택안함 
    bf(st, idx+1); 

}

int main() {

    string st; // 암호  
    char ch;    

    cin >> L >> C; //C개 중에 L개를 골라 암호 만들기  

    for(int i = 0; i < C; i++){    // 주어진 문자 
        cin >> ch;
        alpha.push_back(ch);
    } // 입력받기 끝 

    sort(alpha.begin(), alpha.end()); // 오름차순 정렬 

    bf(st, 0); // 모든 조합 시도 

    return 0;
}