[백준/C] 1759 - 암호 만들기

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

해결 과정

사전순으로 출력하기 위해서는, 알파벳을 입력받은 후 정렬을 해준 다음에 재귀함수로 보내야 한다. 이를 위해 qsort를 사용했다.

일반적인 dfs 함수를 사용하되, 문제에서 주어진 조건인 최소 1개의 모음, 최소 2개의 자음으로 되어 있는지 검사하는 부분을 추가해야 된다.

void password(int start, int c, int l, char letters[], char current[], int depth) {
    if (depth == l) {
        int vowelCount = 0;
        int consCount = 0;

        for (int i = 0; i < l; i++) {
            if (isVowel(current[i]))
                vowelCount++;
            else
                consCount++;
        }

        if (vowelCount >= 1 && consCount >= 2) {
            for (int i = 0; i < l; i++)
                printf("%c", current[i]);
            printf("\n");
        }
        return;
    }

    for (int i = start; i < c; i++) {
        current[depth] = letters[i];
        password(i + 1, c, l, letters, current, depth + 1);
    }
}

• depth == l 이라면 l개의 숫자를 모두 뽑은 것이므로 모음, 자음 조건을 검사하고 만족한다면 출력한다.
• depth != l 인 경우 letters[i]를 current[depth]에 저장해주고, start 자리에는 i + 1, depth 자리에는 depth + 1 을 전달해주면서 재귀호출한다.

전체 코드

#include <stdio.h>
#include <stdlib.h>

int isVowel(char c) {
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

int compare(const void *a, const void *b) {
    return *(char *)a - *(char *)b;
}

void password(int start, int c, int l, char letters[], char current[], int depth) {
    if (depth == l) {
        int vowelCount = 0;
        int consCount = 0;

        for (int i = 0; i < l; i++) {
            if (isVowel(current[i]))
                vowelCount++;
            else
                consCount++;
        }

        if (vowelCount >= 1 && consCount >= 2) {
            for (int i = 0; i < l; i++)
                printf("%c", current[i]);
            printf("\n");
        }
        return;
    }

    for (int i = start; i < c; i++) {
        current[depth] = letters[i];
        password(i + 1, c, l, letters, current, depth + 1);
    }
}

int main() {
    int l, c;
    scanf("%d %d", &l, &c);

    char *current = (char *)malloc(sizeof(char) * l);
    char *letters = (char *)malloc(sizeof(char) * c);
    for (int i = 0; i < c; i++)
        scanf(" %c", &letters[i]);
    
    qsort(letters, c, sizeof(char), compare);

    password(0, c, l, letters, current, 0);
    free(letters);
    return 0;
}