[BOJ 1759] 암호 만들기

1759번: 암호 만들기

 

1. 문제 설명

암호의 조건을 다시 정리하면 아래와 같다.

1. 1개 이상의 모음이 있어야 함
2. 2개 이상의 자음이 있어야 함
3. 암호를 이루는 알파벳이 증가하는 순서일 것

 

2. 구현 아이디어 1 - 시간 초과

구현 문제라고 생각하고, 순열을 구할 때 사용하는 next_permutation을 활용하여 문제에 주어진 조건대로 구현하였다.

하지만 결과는 시간 초과 🥲

 

#include <bits/stdc++.h>

using namespace std;

int l, c;
vector<char> v;
char vowel[5] = {'a', 'e', 'i', 'o', 'u'};

bool check(string s) {
    // 모음의 개수를 count
    int cnt = 0;

    for (auto v : vowel) {
        if (s.find(v) != string::npos) cnt++;
    }

    // 모음의 개수가 1개 이상, 자음의 개수가 2개 이상
    if (cnt >= 1 && s.size() - cnt >= 2) {
        // 문자열의 ASCII 번호가 증가하는 순서
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] > s[i+1]) return false;
        }
        return true;
    } else return 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()); // next_permutation을 사용하려면 오름차순이어야 함

    // next_permutation(순열) 활용
    do {
        string s = "";
        for (int i = 0; i < l; ++i) {
            s += v[i];
        }

        if (check(s)) cout << s << "\n";

        reverse(v.begin() + l, v.end());
    } while (next_permutation(v.begin(), v.end()));

    return 0;
}

 

nPr이 최대가 나올 때는 r=n/2일 때이다. 문제에 3 ≤ L ≤ C ≤ 15라고 주어졌기 때문에 대충 15P7이 3000만 정도이기 때문에 시간 제한이 넉넉하다고 생각했다.

하지만! 문제가 틀리고 15P8을 계산해봤는데 ...! 약 2억 6천이 나왔다 ...

 

그렇기 때문에 worst case의 경우 next_permutation만 계산해도 시간 초과가 나는 것이였다.

 

3. 구현 아이디어 2 - 틀렸습니다

next_permutation을 사용하면 주어진 시간 내에 풀기 어려울 것 같아 재귀를 사용하여 상태공간트리로 풀어보았다.

 

벡터 v를 정렬하여 다음 자리에 올 알파벳은 무조건 지금 알파벳보다 크도록 하였다.

 

정렬한 상태의 벡터에서 순차 탐색을 하면 위와 같은 예시에서 c 뒤에는 i, s, w, t만 올 수 있으므로 암호가 오름차순으로 이루어졌는지 검사하는 로직을 별도로 만들지 않아도 된다.

 

그리고 마지막에 재귀 탈출을 할 때 조건문으로 모음과 자음의 개수를 확인하여 조건을 충족(모음 1개 이상, 자음 2개 이상)하는 경우에만 암호를 출력하도록 코드를 구성하였다.

#include <bits/stdc++.h>

using namespace std;

int l, c;
vector<char> v;
vector<char> vowel = {'a', 'e', 'i', 'o', 'u'};

// 모음일 경우 1, 자음일 경우 0을 반환
int isVowel(char c) {
    if ((find(vowel.begin(), vowel.end(), c) != vowel.end())) return 1;
    else return 0;
}

// idx - 벡터 v에서 현재 문자의 index
// cnt - 모음의 개수
void password(string s, int idx, int cnt) {
    // 문자열의 길이가 l이 됐을 때 재귀 탈출
    if (s.size() == l) {
        // 모음이 1개 이상, 자음이 2개 이상
        if (cnt >= 1 && s.size()-cnt >= 2) cout << s << "\n";
        return;
    }

    for (int i = idx+1; i < c; ++i) {
        password(s+v[i], i, cnt + isVowel(v[i]));
    }
}

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());

    for (int i = 0; i < l; ++i) {
        string s;
        int cnt = isVowel(v[i]);

        password(s+v[i], i, cnt);
    }
    return 0;
}

 

26%쯤 진행하다 틀렸습니다가 떴다.

 

4. 구현 아이디어 2 - 맞았습니다!!

질문 게시판에 있는 반례들을 넣어봤지만 해결되지 않았다😞 다른 사람들의 블로그들을 보다 반복문에서 재귀 함수를 호출할 때의 범위가 나와 다른 것을 찾을 수 있었다.

 

기존에는 i가 끝나는 범위를 i<l로 했었는데 이렇게 할 경우 놓치게 되는 암호가 있다는 것을 알게 되었고 c-l로 수정하여 해결할 수 있었다.

# Input
3 6
a b c d e f

일 때, i<l일 때는 암호의 첫 글자가 a, b, c만 가능하다. 하지만 실제로는 def도 암호가 될 수 있다.

 

main 함수에서 for문의 범위를 아래와 같이 수정해주었다.

for (int i = 0; i <= c-l; ++i) {
    string s;
    int cnt = isVowel(v[i]);

    password(s+v[i], i, cnt);
}