[BOJ] 1759. 암호만들기

문제

BOJ 1759. 암호만들기

풀이

입력을 사전 순으로 정렬하기 위해 Arrays.sort()를 사용했다.
조합을 이용하여 dfs() + 백트래킹을 구현했다.
cnt==C라는 기저조건을 만족했을 때 최소 모음과 자음의 개수를 체크하고 만족했을 때 결과를 출력하도록 했다.

JAVA코드

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

public class 백준1759_암호만들기 {
	static int L,C;
	static char[] alpha;
	static char[] result;
	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());
		
		alpha = new char[C];
		result = new char[L];

		st = new StringTokenizer(br.readLine());
		for(int i=0;i<C;i++) {
			alpha[i] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(alpha);
		
		dfs(0,0);
		
	}
	
	public static void dfs(int index,int cnt) {
		
		if(cnt==L) {
			StringBuilder sb = new StringBuilder();
			int m = 0;
			int j = 0;
			for(int i=0;i<L;i++) {
				char ch = result[i];
				if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u') m++;
				else j++;
				sb.append(ch);
			}
			
			if(m>=1&&j>=2) System.out.println(sb);
			return;
		}
		if(index==C) return;
		
		result[cnt]=alpha[index];
			dfs(index+1,cnt+1);
			dfs(index+1,cnt);
	}
}