[백준] 1759번 암호 만들기 (JAVA)

문제

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

1759번: 암호 만들기

 

설명

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다.
암호를 이루는 알파벳은 암호에서 증가하는 순서로 배열되어 있다.

먼저, 입력받은 알파벳을 알파벳 순서대로 정렬한다.

자릿수는 L이고 알파벳 수는 C이므로 암호의 첫 알파벳은 input[0] ~ input[C-L] 이 될 수 있다. 

암호의 길이를 나타내는 length, 모음의 개수를 나타내는 vowel, 자음의 개수를 나타내는 consonant을 모두 초기값으로 0으로 설정하고 DFS을 진행한다.

st = new StringTokenizer(br.readLine());
input = new char[C];
for (int i = 0; i < C; i++) {
    input[i] = st.nextToken().charAt(0);
}
        
// 알파벳 순서대로 정렬
Arrays.sort(input);

for (int i = 0; i <= C - L; i++) {
    length = 0;
    vowel = 0;
    consonant = 0;
    
    dfs(i);
}

인자로 받은 문자가 모음인지 판단하는 함수인 isVowel()을 이용해 DFS을 진행하면서 length, vowel, consonant 값을 조정한다. length 값이 L이 되는 순간에 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있는지 체크한다.

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

static void dfs(int index) {
    // 1. 체크인
    visited[index] = true;
    if (isVowel(input[index]) 
        vowel++;
    else
        consonant++;
    length++;

    // 2. 목적지인가?
    if (length == L) {
        if (vowel >= 1 && consonant >= 2) {
            for (int i = 0; i < C; i++) {
                if (visited[i])
                    System.out.print(input[i]);
            }
            System.out.println();
        }
    }
    else {
        // 3. 연결된 곳을 순회
        for (int i = index + 1; i < C; i++) {
            // 4. 갈 수 있는가?
            // 5. 간다
            dfs(i);
        }
    }

    // 6. 체크아웃
    visited[index] = false;
    if (isVowel(input[index]))
        vowel--;
    else
        consonant--;
    length--;
}

 

전체 코드

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

public class Main {

    static int L, C, length, vowel, consonant;
    static boolean[] visited;
    static char[] input;

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

    static void dfs(int index) {
        // 1. 체크인
        visited[index] = true;
        if (isVowel(input[index]))
            vowel++;
        else
            consonant++;
        length++;

        // 2. 목적지인가
        if (length == L) {
            if (vowel >= 1 && consonant >= 2) {
                for (int i = 0; i < C; i++) {
                    if (visited[i])
                        System.out.print(input[i]);
                }
                System.out.println();
            }
        }
        else {
            // 3. 연결된 곳을 순회
            for (int i = index + 1; i < C; i++) {
                // 4. 갈 수 있는가?
                // 5. 간다
                dfs(i);
            }
        }

        // 6. 체크아웃
        visited[index] = false;
        if (isVowel(input[index]))
            vowel--;
        else
            consonant--;
        length--;
    }

    public static void main(String[] args) 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());

        visited = new boolean[C];

        st = new StringTokenizer(br.readLine());
        input = new char[C];
        for (int i = 0; i < C; i++) {
            input[i] = st.nextToken().charAt(0);
        }

        // 알파벳 순서대로 정렬
        Arrays.sort(input);

        for (int i = 0; i <= C - L; i++) {
            length = 0;
            vowel = 0;
            consonant = 0;
            dfs(i);
        }
    }
}