[BOJ] 1759번 : 암호 만들기 (C++)

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

코드 구현의 아이디어는 next_permutation 함수로 6개 중 4개를 뽑는 조합을 모두 만든다.

그 중에서 모음이 최소 한 개, 자음이 최소 두 개인지의 조건만 추가로 체크해주고 이 조건이 통과되면 개수를 세어주었다. 

next_permutation은 c++로 코팅을 하는 사람인 경우 조합을 구해야할 때 사용할 수 있는 아주 사기적인 함수이다. 

(모르는 분은 검색하여 보길 추천한다.)

 

next_permutation 함수는 순열을 사용할 때 쓰는 함수이다.

그래서 조합을 구할 때 쓰기 위해선 choose배열처럼 {0,0,0,0,1,1} 형태의 배열이 따로 필요하다.

choose배열을 next_permutation을 돌리면서 choose값이 0인 경우에만 답을 출력해주면 된다. 

그런데 지금은 모음 한 개 이상, 자음 두 개 이상이라는 조건이 필요하므로 check함수를 두어 조건을 확인하였다. 

 

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

int l, c, cnt;
char arr[18];
int choose[18];
char mo[5]={'a','e','i','o','u'};

bool check(){
    int cnt=0; //모음개수 카운트

    for(int i=0; i<c; i++){
        for(int j=0; j<5; j++){
            //예제1로 보면 6개 중 선택된 4개만 모음하고 비교하기
            if(choose[i]==0){
                if(arr[i]==mo[j]) cnt++;
            }
        }
    }
    if(cnt>=1 && l-cnt>=2) return 1; //모음 1개, 자음 2개 이상일 때만 참
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    //next_permutation함수로 6개 중 4개를 뽑는 조합을 만듦
    //그 중에서 모음 최소 한 개, 자음 최소 두 개인지 조건 체크한 후 cnt++
    cin>>l>>c;
    for(int i=0; i<c; i++) cin>>arr[i];
    
    //choose배열 전부 1로 초기화하고 앞에서부터 L개만 0으로 채움
    for(int i=0; i<18; i++) choose[i]=1;
    for(int i=0; i<l; i++) choose[i]=0;

    //정렬하기
    sort(arr, arr+c);

    do
    {
        if(check()){ //모음,자음 조건이 맞다면
            for(int i=0; i<c; i++){
                if(choose[i]==0) {
                    cout<<arr[i];
                }
            }
            cout<<'\n';
        }
    } while (next_permutation(choose,choose+c));
    
}

 

 

 

 

이번에는 바킹독의 코드이다. 

나의 코드와 아이디어는 비슷하나 choose라는 배열 대신 brute라는 vector를 사용하여 vector<int> brute(c);로 두었다. 

vector는 생성할 때 초기화를 할 수 있는데, vector<int> vec(3,-1); 이라고 한다면 크기 3짜리 int형 벡터가 만들어지고 각각은 -1로 초기화된다. 그냥 vector<int> vec(3); 이라고 하면 0으로 자동 초기화된다. 

바킹독은 조합을 만드는 동안 string ans을 두어서 ans에 글자를 하나씩 저장함과 동시에 이게 모음에 해당하는지 확인한다. 

 

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

int l, c, cnt;
char arr[18];

bool aeiou(char x){
    return x=='a'||x=='e'||x=='i'||x=='o'||x=='u';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>l>>c;
    for(int i=0; i<c; i++) cin>>arr[i];
    sort(arr, arr+c); //정렬하기
    
    vector<int> brute(c);
    for(int i = l; i < c; i++) brute[i] = 1;
    
    //next_permutation함수로 6개 중 4개를 뽑는 조합을 만듦
    //하나씩 뽑을 때마다 str에 저장해주고 동시에 자음인지 체크하기
    do
    {
        string str; //뽑힌 4개를 저장할 변수
        int cnt=0;
        for(int i=0; i<c; i++){
            if(brute[i]==0) {
                str+=arr[i];
                cnt+=aeiou(arr[i]);
            }
        }
        if(cnt>=1&&l-cnt>=2) cout<<str<<'\n';
    } while(next_permutation(brute.begin(),brute.end()));
}

 

회고1) 내 코드에서 check함수 안에 자음이 2개인지를 체크하는 부분을 계속 c-cnt라고 두어서 틀렸었다...ㅎ 그리고 그렇게 한 번 틀리니깐 바로 답을 찾아봐버렸다. . 앞으로는 내 코드에서 어디가 틀린건지 좀 더 꼼꼼히 보고 저런 디테일한 부분 조심해야겠다.

 

회고2)

바킹독의 코드는 확실히 깔끔하고 길이도 훨씬 짧아서 더 좋은 코드라고 생각된다. 

이런 좋은 아이디어들을 내것으로 만들어야 될 것 같다.