[ 백준 ][ 자바 ][ 1759 ] 암호만들기 retry

로또랑 정말 비슷한 문제인데

자음 2개 모음 1개가 있다는 조건만 추가된 문제

dfs 개념 잡기에는 로또랑 이문제가 순차적으로 풀면 정말 좋을것같다!

 

중간에 멘붕나고 맘이 이상해져서 그냥 막풀어서 최적화를 못했다.ㅎ/..

 

package back;

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

public class Main_backjoon_1759_암호만들기_retry {
	static String[] vowel = {"a","e","i","o","u"};
	static int L;
	static int C;
	static String[] arr;
	static boolean[] visit;
	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());
		visit = new boolean[C];
		arr = new String[C];
		arr = br.readLine().split(" ");
		Arrays.sort(arr);
		
	
//		for(int i = 0; i < arr.length; i++) {
//			System.out.print(arr[i] + " " );
//			System.out.println((int) arr[i].charAt(0));
//		}
		dfs(0,0);
	}
	public static void dfs(int start, int depth) {
		//System.out.println(depth);
		//출력 
		if( depth == L ) {
			//검사용
			boolean isPossible = false;
			int isPossible2 = 0;
			//모음
			for(int i = 0 ; i < C; i++) {
				if(visit[i]) {
					if ( isPrommising(arr[i])) {
						isPossible = true;
					}
				}
			}
			//자음
			for(int i = 0 ; i < C; i++) {
				if(visit[i]) {
					if ( !isPrommising2(arr[i])) {
						isPossible2 +=1;
					}
				}
			}
			
			if( isPossible  && isPossible2 >= 2) {
				for(int i = 0 ; i < C; i++) {
					if(visit[i]) {
						System.out.print(arr[i]);
					}
				}
				System.out.println();
			}
			return;
		}
		
		for(int i = start; i < C; i++) {
			visit[i]  = true;
			dfs(i + 1 , depth + 1 );
			visit[i]  = false;
		}
	}
	public static boolean isPrommising(String str) {
		boolean flag = false;
		for(int i = 0 ; i< vowel.length; i++) {
			if( vowel[i].equals(str)) {
				flag =true;
			}
		}
		return flag;
	}
	public static boolean isPrommising2(String str) {
		boolean flag = false;
		for(int i = 0 ; i < vowel.length; i++) {
			if( vowel[i].equals(str)) {
				flag = true;
			}
		}
		return flag;
	}

}