백준 1759 : 암호 만들기

문제 링크입니다 https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

재귀 함수를 이용해 모든 경우를 탐색하는 방식으로 문제를 해결했습니다. 두 가지 방법으로 구현하였습니다. 자세한 설명은 주석을 참고하시면 될 것 같습니다!

 

 

[소스코드 1]

 

#include<algorithm>
#include<cstdio>
using namespace std;
 
int L, C;
 
// 문자를 고를 때 중복을 방지하기 위한 check 배열
// 입력받은 문자들 중 자음과 모음을 구별하기 위한 check2 배열
bool check[20], check2[50];
 
// 입력받을 alpha 배열, 문자를 골라서 암호를 만들기 위한 result 배열
char alpha[20], result[10];
 
// result[count]에 문자를 하나씩 채워가며 암호를 만들어 주어진 길이가 되면
// 최소 자음 개수, 최소 모음 개수를 확인하여 가능한 암호를 출력해주는 함수
void getResult(int count, int start) {
 
    // 내가 L개의 문자를 골랐다면
    if (count == L) {
 
        // 자음과 모음의 개수를 세어줍니다
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < count; i++) {
            if (check2[result[i] - 'a']) cnt1++;
            else cnt2++;
        }
 
        // 모음이 1개 이상, 자음이 2개 이상이 아니면 출력하지 않습니다
        if (!(cnt1 >= 1 && cnt2 >= 2)) return;
 
        // 위 if문에 걸리지 않는다면 가능한 암호이므로 출력합니다
        for (int i = 0; i < count; i++) {
            printf("%c", result[i]);
        }
        printf("\n");
        return;
    }
    // i를 start부터 시작하고 getResult 함수의 i+1을 인자로 주는 이유는
    // 알파벳이 증가하는 순서로 암호를 만들어야 하므로 오름차순인 배열에서
    // 항상 내 다음 문자를 골라야 하기 때문입니다
    for (int i = start; i < C; i++) {
        if (!check[i]) {                  // 내가 고른적이 없으면
            check[i] = true;              // 골라주고
            result[count] = alpha[i];     // result[count]에 그 문자를 넣고
            getResult(count + 1, i + 1);  // result의 다음 칸을 채우러 갑니다
            result[count] = '\0';         
            check[i] = false;
        }
    }
}
 
int main(void) {
 
    scanf("%d%d", &L, &C);
    for (int i = 0; i < C; i++) {
        scanf(" %c", &alpha[i]);
        char x = alpha[i];
 
        // 입력받은 문자가 모음이면 true
        if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
            check2[x - 'a'] = true;  
        }
    }
    sort(alpha, alpha + C);    // 오름차순으로 정렬합니다
    getResult(0, 0);
 
    return 0;
}

 

 

[소스코드 2]

 

#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
using namespace std;
 
int L, C;
 
// 내가 만든 문자열이 최소 모음, 최소 자음 개수를 만족하는지 확인해주는 함수
bool check(string &password) {
    int cnt1 = 0, cnt2 = 0;
 
    // go 함수에서 password를 출력하는 for문과 동일하게 작동하는 코드입니다
    for (char x : password) {
        if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') cnt1++;
        else cnt2++;
    }
 
    // 모음 개수가 1 이상이고 자음 개수가 2 이상이면 true
    // 아니면 false를 반환
    return cnt1 >= 1 && cnt2 >= 2;
}
 
// 재귀 호출을 통해 password에 문자를 하나씩 채우면서 길이가 L이 되면
// check 함수를 통해 가능한 암호인지 확인하고 출력해주는 함수
void go(int n, vector <char> &a, string password, int idx) {
 
    // 내가 길이 L의 문자열을 만들었으면
    if (password.length() == L) {
 
        // 가능한 암호인지 확인하고 가능하다면
        if (check(password)) {
 
            // 출력합니다
            for (int i = 0; i < L; i++) {
                printf("%c", password[i]);
            }
            printf("\n");
        }
        return;
    }
    // 더 이상 고르거나 고르지 않을 문자가 없을 때
    if (idx == a.size()) return;
 
    go(n, a, password + a[idx], idx + 1);  // 문자를 고르는 경우
    go(n, a, password, idx + 1);           // 문자를 고르지 않는 경우
}
 
int main(void) {
 
    scanf("%d%d", &L, &C);
    vector <char> a(C);
    
    for (int i = 0; i < C; i++)
        scanf(" %c", &a[i]);    // a 배열에 문자를 입력받습니다
 
    sort(a.begin(), a.end());   // 오름차순으로 정렬해줍니다
    go(L, a, "", 0);
    return 0;
}