[백준] 1759번 - 암호 만들기 (Gold 5)

문제 링크

[백준] 1759번 - 암호 만들기 (Gold 5)

문제 설명

암호의 길이 L과 암호에 들어갈 수 있는 c가지 문자가 주어져 있다.
암호는 다음의 세 가지 조건을 만족한다.

1. 암호는 서로 다른 L개의 알파벳 소문자로 구성되어 있다.
2. 알파벳은 오름차순으로 배열되어 있다.
3. 암호에는 최소 한 개의 모음과 최소 두 개의 자음이 들어있다.

가능성 있는 암호들을 사전순으로 출력하시오.

정답 코드 및 설명

모든 경우를 백트래킹으로 탐색해서 가능한 경우만을 출력하면 된다.
처음에 주어진 가능한 문자들을 미리 정렬해두면 암호의 2번 조건을 확인하기가 편하다.
풀고 나서 코드를 다시 보니 모음의 최소 개수인 1과 자음의 최소 개수인 2를 따로 상수로 지정하는 것이 더 좋아보인다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1759 {
    int l, c;
    char[] letters;
    char[] code;
    int vowel = 0;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        letters = new char[c];
        code = new char[l];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < c; i++)
            letters[i] = st.nextToken().charAt(0);
        Arrays.sort(letters);
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    void printCode(int depth) throws IOException {
        if (depth == l) {
            if (vowel < 1 || vowel > l - 2) return;
            bw.write(code);
            bw.flush();
            bw.newLine();
            return;
        }
        for (char c : letters) {
            if (depth == 0 || code[depth - 1] < c) {
                if (isVowel(c)) vowel++;
                code[depth] = c;
                printCode(depth + 1);
                code[depth] = ' '; // 공백의 유니코드 값은 알파벳 소문자들보다 작다
                if (isVowel(c)) vowel--;
            }
        }
    }

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

    void solution() throws IOException {
        input();
        printCode(0);
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new BOJ1759().solution();
    }
}