[백준][1759] 암호만들기

문제 URL

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

나의 풀이

package backjoon;

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static char[] arr;
    static char[] ans;
    static final int MIN_M = 1; // 최소 모음개수
    static final int MIN_N = 2; //최소 자음개수


    public static void main(String args[]) throws IOException {
        StringTokenizer str = new StringTokenizer(br.readLine());
        StringTokenizer str2 = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(str.nextToken());
        int c = Integer.parseInt(str.nextToken());
        ans = new char[l];
        arr = new char[c];
        for (int i = 0; i < c; i++) {
            arr[i] = str2.nextToken().charAt(0);
        }
        Arrays.sort(arr);
        cal(0, 0, l, c, 0, 0);
        bw.flush();
        bw.close();
    }

    /*
    l : 비밀번호 자리수
    c : 비밀번호 후보문자 총개수
    m : 모음개수
    n : 자음 개수
     */
    public static void cal(int idx, int selected, int l, int c, int n, int m) throws IOException {
        if (selected == l) {
            //최소 모음,자음 개수 만족하지 못하면 출력x
            if (n < MIN_N || m < MIN_M) return;

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < l; i++)
                sb.append(ans[i]);
            bw.write(sb.toString());
            bw.newLine();
            return;
        }

        if (idx >= c)
            return;

        int a=0, b=0;
        if (arr[idx] == 'a' || arr[idx] == 'e' || arr[idx] == 'i' || arr[idx] == 'o' || arr[idx] == 'u') {
            a++;
        } else {
            b++;
        }

        ans[selected] = arr[idx];
        cal(idx + 1, selected + 1, l, c, n+b, m+a);
        ans[selected] = 0;
        cal(idx + 1, selected, l, c, n, m);
    }
}

느낀점

시간복잡도 : o(2c)