백준 1759번 : 암호 만들기(Java)

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

1759번: 암호 만들기

---

[풀이]

• 브루트포스 유형의 문제였으며 DFS를 이용해 풀었습니다.
• 구현해야하는 조건은 3가지였습니다.
  • 모음이 최소 1개 포함되야 한다.
  • 자음이 최소 2개 포함되야 한다.
  • 길이가 L이어야 합니다.
  • 이 두가지를 확인하는 메소드를 구현했습니다.
• dfs 메소드를 재귀적으로 호출하면서 출력합니다.

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int L, C;
    static String[] arr;

    public static boolean check(String input) {
        int consonant = 0;
        int vowel = 0;
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == 'a' || input.charAt(i) == 'e' || input.charAt(i) == 'i' || input.charAt(i) == 'o' || input.charAt(i) == 'u')
                vowel += 1;
            else
                consonant += 1;
        }
        if (vowel < 1 || consonant < 2)
            return false;
        else
            return true;
    }

    public static void solve(int idx, String str) {
        if (str.length() == L && check(str)) {
            System.out.println(str);
            return;
        }
        if (idx >= C)
            return;

        solve(idx + 1, str + arr[idx]);
        solve(idx + 1, str);
    }

    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());
        st = new StringTokenizer(br.readLine(), " ");
        arr = new String[C];
        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken();
        }

        Arrays.sort(arr);

        solve(0, "");
    }
}