백준 1759번 암호 만들기 (C++)

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

1759번: 암호 만들기

이 문제는 백준 15655번 N과 M(6)과 유사하다.

 

문제 풀이는 다음과 같다. 

 

1. 문자열을 입력받고 정렬해준다. 이는 정답을 사전식으로 출력하기 위해서이다.

2. 문자열을 사전식으로 쌓기 위한 함수를 정의해준다. 

이때 함수에서 넘겨받는 인자는 3가지가 있는데, 시작지점과 문자의 저장 위치, 저장된 문자의 갯수로 총 3가지 이다.

void go(int start, int index, int cnt){ ... }

3. 시작지점을 넘겨받는 이유는 무조건 오름차순으로만 답을 저장하기 위함이며, 이로인하여 문자가 역순으로 저장되는 것을 방지하기 위해서이다. 문자의 저장 위치를 넘겨받는 이유는 마찬가지로 오름차순으로 답을 출력하기 위함이다.

4. 문자열의 사이즈가 입력받은 값 l과 동일하면, 해당 문자열이 모음을 1개 이상 가지고 있고 자음을 2개 이상 가지고 있는지 확인한다.

5. 4번이 충족되면 문자열을 출력하고 return 한다.

 

[index로 문자를 저장한 버젼]

#include <iostream>
#include <algorithm>
#include <vector>
const int MAX = 16;
using namespace std;

int l=0,c=0;
char temp[MAX];
vector<char> v;
bool ch[MAX] = {false,};

void go(int start, int index, int cnt){
    if(cnt==l){
        bool vo = false; // 모음
        int con = 0; // 자음 갯수
        for(int i=0; i<l; i++){
            if(temp[i]=='a'||temp[i]=='e'||temp[i]=='i'||temp[i]=='o'||temp[i]=='u') { vo = true;}
            else con++;
        }
        if(vo&&con>=2){
            for(int i=0; i<l; i++) cout << temp[i];
            cout << "\n";
        }
        return;
    }
    for(int i=start; i<v.size(); i++){
        if(!ch[i]){
            ch[i] = true;
            temp[index] = v[i];
            go(i+1, index+1,cnt+1);
            ch[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> l >> c;
    for(int i=0; i<c; i++){
        char temp;
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(),v.end());
    go(0,0,0);
    return 0;
}

 

[문자열을 활용해 값을 저장한 버전] 

#include <iostream>
#include <algorithm>
#include <vector>
const int MAX = 16;
using namespace std;

int l=0,c=0;
vector<char> v;
bool ch[MAX] = {false,};

void go(int start, string s){
    if(s.size()==l){
        bool vo = false; // 모음
        int con = 0; // 자음 갯수
        for(int i=0; i<s.size(); i++){
            if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u') vo = true;
            else con++;
        }
        if(vo&&con>=2) cout << s << "\n";
        return;
    }
    for(int i=start; i<v.size(); i++){
        if(!ch[i]){
            ch[i] = true;
            go(i+1, s+v[i]);
            ch[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> l >> c;
    for(int i=0; i<c; i++){
        char temp;
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(),v.end());
    go(0,"");
    return 0;
}

이 버젼이 훨씬 쉽고 간결하다.

 

자음이 2개이상 있어야 한다는 조건을 빼먹어서, 처음 제출 시 약 30%가량 넘겼을때 틀리고 말았다.