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

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

1759번: 암호 만들기

 

풀이

순열을 이용한 조합 방법이 있어서 적용시켜봤다.

 

vector<bool> n을 사용했는데 { 1, 1, 1, 0, 0, 0, 0 } 의 꼴로 저장한 다음 이전 순열로 돌려주면 마지막엔 { 0, 0, 0, 0, 1, 1, 1 } 이 된다.

여기서 1 에 해당하는 배열 위치의 값을 추출하면 조합이 된다.

 

{ 1, 1, 1, 0, 0, 0, 0 }

{ a, b, c, d, e, f, g }

 

여기서 부터 시작해서 

 

 

{ 0, 0, 0, 0, 1, 1, 1 }

{ a, b, c, d, e, f, g } 

 

까지 진행된다.

 

이전 순열로 돌려주는 이유는 출력을 사전 순으로 하기 위함이다.

 

 

그리고 출력은 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있는 조건을 달아주면 된다.

 

전체 코드

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

using namespace std;

int L, C;
vector<char> v;
vector<bool> n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> L >> C;

    for (int i = 0; i < C; i++) {
        char c;
        cin >> c;
        v.push_back(c);
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < L; i++) n.push_back(true);
    for (int i = L; i < C; i++) n.push_back(false);

    do {
        vector<char> s;
        int aeiou = 0;

        for (int i = 0; i < C; i++) {
            if (n[i] == 1) {
                if(v[i] == 'a' || v[i] == 'e' || v[i] == 'i' || v[i] == 'o' || v[i] == 'u') aeiou++;
                s.push_back(v[i]);
            }
        }
        if (aeiou == 0 || L - aeiou < 2) continue;
        for (auto i : s) cout << i;
        cout << '\n';

    } while (prev_permutation(n.begin(), n.end()));
}