[백준] 1759번 : 암호 만들기

문제

 

---

풀이

 

사전순으로 출력하라고 했으니까 일단 문자 입력을 정렬해야할 것이다.

백트래킹으로 C길이의 문자열을 만들고, 이 문자열이 모음 1개 이상, 자음 2개 이상의 규칙을 충족하는지 확인하면 된다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int L, C;
char input[15], arr[15];

bool isPromising() {
    int vowel = 0;
    for (int i = 0; i < L; i++) {
        if ((arr[i] == 'a') || (arr[i] == 'e') || (arr[i] == 'i') || (arr[i] == 'o') || (arr[i] == 'u')) //모음 개수 확인
            vowel++;
    }
    if ((vowel >= 1) && ((L - vowel) >= 2)) //자음, 모음 개수 확인
        return true;
    return false;
}

void backtracking(int idx, int num) {
    if (num == L) {
        if (isPromising()) { //자음, 모음 개수 확인 후 출력
            for (int i = 0; i < L; i++)
                cout << arr[i];
            cout << '\n';
        }
        return;
    }
    for (int i = idx + 1; i < C; i++) { //오름차순으로 탐색하기 위해
        arr[num] = input[i];
        backtracking(i, num + 1);
    }
}

int main() {
    cin >> L >> C;
    for (int i = 0; i < C; i++)
        cin >> input[i];
    sort(input, input + C); //정렬
    backtracking(-1, 0);
}

전체 소스코드다.

 

int main() {
    cin >> L >> C;
    for (int i = 0; i < C; i++)
        cin >> input[i];
    sort(input, input + C); //정렬
    backtracking(-1, 0);
}

메인에선 백트래킹 함수를 호출하기 전 정렬을 해준다.

 

void backtracking(int idx, int num) {
    if (num == L) {
        if (isPromising()) { //자음, 모음 개수 확인 후 출력
            for (int i = 0; i < L; i++)
                cout << arr[i];
            cout << '\n';
        }
        return;
    }
    for (int i = idx + 1; i < C; i++) { //오름차순으로 탐색하기 위해
        arr[num] = input[i];
        backtracking(i, num + 1);
    }
}

그냥 평범한 백트래킹 함수이다.

오름차순이란 조건이 있기 때문에 굳이 따로 visited 관련 배열을 만들 필요가 없다.

 

백트래킹의 종료조건에 다다르면 isPromising 함수로 이 문자열이 암호의 조건을 충족하는지 확인한다.

 

bool isPromising() {
    int vowel = 0;
    for (int i = 0; i < L; i++) {
        if ((arr[i] == 'a') || (arr[i] == 'e') || (arr[i] == 'i') || (arr[i] == 'o') || (arr[i] == 'u')) //모음 개수 확인
            vowel++;
    }
    if ((vowel >= 1) && ((L - vowel) >= 2)) //자음, 모음 개수 확인
        return true;
    return false;
}

isPromising 함수는 별거 없다.