[백준] 1759 암호 만들기

문제 출처: www.acmicpc.net/problem/1759

1759번: 암호 만들기

: 주어진 문자들로 L길이의 암호를 만들어야 한다.

: 암호의 조건은 최소 한 개의 모음과 최소 두 개의 자음을 포함하는 것이다.

: 또한 그 암호들이 정렬되어 있어야 하기 때문에 조합을 하기 전에 미리 정렬시켜 놓는다.

: 먼저 주어진 문자들로부터 L개를 뽑는 조합 함수를 만든다.

: L개를 뽑은 후에는 그 L개에 암호의 조건이 부합한지를 판단한다.

: 조건에 부합하는 지는 해당 암호를 순회하며 자음과 모음의 개수를 세고 마지막에 그 개수가 조건을 만족하는지를 보면 된다.

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

public class 암호만들기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int L, C;
	static char[] str;
	static boolean[] v;
	static char[] ans;
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		v = new boolean[C];
		str = new char[C];
		ans = new char[L];
		// 입력받기
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			str[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(str);
		comb(0,0);
		System.out.println(sb);
		// 길이 L의 조합을 해보고
		// 최소 한개의 모음과 최소 두개의 자음이 들어있는지 확인
	}
	static int count = 0;
	static char[] chk = {'a', 'e', 'i', 'o', 'u'};
	private static void comb(int idx, int cnt) {
		if(cnt == L) {
			// 여기서 최소 한개의 모음과 최소 두개의 자음이 있는지 확인
//			System.out.println(Arrays.toString(ans));
			if(check(ans)) {
				for(int i = 0; i < L; i++) sb.append(ans[i]);
				sb.append("\n");
			}
			return;
		}
		for(int i = idx; i < C; i++) {
			ans[cnt] = str[i];
			comb(i+1, cnt+1);
		}
	}
	private static boolean check(char[] ans) {
		int count1 = 0; // 모음 카운터
		int count2 = 0; // 자음 카운터
		for(int i = 0; i < L; i++) {
			boolean flag = false;
			for(int j = 0; j < 5; j++) {
				if(ans[i] == chk[j]) {
					count1++;
					flag = true;
					break;
				}
			}
			if(!flag)count2++;
		}
		if(count1 > 0 && count2 > 1) return true;
		return false;
	}
}