백준 1759번 암호 만들기 JAVA

링크텍스트

설명

백트래킹을 사용하여 가능한 암호를 생성할 때 각 문자가 모음인지 자음인지 판별하며 모음과 자음의 개수를 각각 세었다.
시간복잡도: O(C!/L!(C-L)!), 공간복잡도: O(L)

코드

import java.util.*;
import java.io.*;

class Main {	
		static int l,c;
		static char [] arr;
		static char [] selected;
		static ArrayList<String> al = new ArrayList<>();
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		l = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		arr = new char[c];
		selected = new char[l];

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

		Arrays.sort(arr);

		dfs(0, 0,0,0);

		for(String s : al){
			sb.append(s).append("\n");
		}

		System.out.print(sb);

	}

	public static void dfs(int depth, int start, int vowel, int consonant){
		if(depth==l){
			if(vowel>=1 && consonant>=2){
				al.add(new String(selected));
			}
			return;
		}

		for(int i=start;i<c;i++){
			selected[depth] = arr[i];

			if(arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u'){
				dfs(depth+1,i+1,vowel+1,consonant);
			}else
				dfs(depth+1,i+1,vowel,consonant+1);
		}
	}
}