문제 이해

알파벳 수열이 미리 주어진다. 이 수열은 패스워드가 될 수 있는 알파벳 후보이다.
패스워드는 2가지 조건을 충족시켜야 한다.

1. 알파벳이 증가하는 순서로 배열되었다.

2. 모음이 1개 이상, 자음이 2개 이상 존재해야 한다.

위의 경우의 수를 모두 만족시키는 경우를 사전 순으로 출력하는 것이 문제이다.

---

문제 풀이

먼저 출력 결과가 사전 순이여야 하기 때문에, 알파벳 후보로 주어진 수열을 Sorting시킨다면 나중에 추가적인 처리 없이 이 조건을 만족시킬 수 있을 것이라 생각하였다.
또한, 알파벳 "증가" 순으로 패스워드는 되어 있기 때문에, 만약 1 ~ k 까지 확인을 한 이후에는 k+1번째 index부터 알파벳 배열을 확인하면 될 것이라고 생각하였다.(Sorting을 미리 진행하였기 때문에 가능한 해결방법)

(ex) (a, b, c, d)가 저장되어 있다고 가정하자. 이 때 ab라는 문자열이 지정된 이후 다음 함수에서 a와 b는 확인하지 않아도 된다. 즉, index = 2부터 arr에서 확인하면 된다.

또한 재귀함수의 Parameter로 자음과 모음 조건을 충족시키는지 확인하는 값들을 넘겨주기로 하였다.

Algorithm은 자음과 모음을 쪼갠 이후 자음의 배열에 넣는 방법도 생각해보았지만, 분기가 너무 많아지고 그렇게 해서 줄일 수 있는 후보군들이 매우 적을 것이라고 생각되었다. 따라서 Brute-Force Algorithm을 활용하였다.

---

코드

import java.util.*;

public class Main {
	static int N, M;
	static Character[] arr; 
    // arr : 패스워드의 후보가 될 알파벳이 저장될 공간
	static StringBuilder sb = new StringBuilder();
	
	static void find(Stack<Character> stack, int index, int length, 
    									boolean check, int num) {
		// stack : 이번 재귀함수 이전까지 담았던 알파벳들이 저장되어 있음
        // index : 이번에 확인해야 할 arr의 첫 index를 의마한다.
        // length : stack의 길이. stack.size()를 사용해도 관계 없다.
        // check : 모음이 하나라도 존재하면 true, 하나도 없다면 False
        // num : 자음의 개수

		if(length==N) {
			if(check && num>=2) {
				String tmp = stack.toString();
				sb.append(tmp.substring(1,tmp.length()-1)
                					.replaceAll(", ","")+"\n");
			}
			return;
		}
		
		for(int i = index;i<M;i++) {
            // i번째 data를 Stack에 넣는 상황이기 때문에 
            // 다음 재귀함수는 i+1부터 확인하면 된다.
            // 따라서, index = i+1로 넘겨준다.
           
			stack.add(arr[i]);
			if(arr[i]=='a' || arr[i] == 'e' || arr[i] == 'i' || 
            							arr[i]=='o' || arr[i]=='u') {
				find(stack, i+1, length+1, true, num);
                // 모음이 패스워드에 들어간 상황
			}else {
				find(stack, i+1, length+1, check, num+1);
                // 자음이 패스워드에 들어간 상황
			}
			stack.pop();
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new Character[M];
		
		for(int i =0;i<M;i++) {
			arr[i] = sc.next().charAt(0);
		}
		Arrays.sort(arr);
		
		find(new Stack<Character>(),0, 0, false, 0);
		
		System.out.println(sb);
	}
}

---

결과