[1759] 암호 만들기

문제 : https://www.acmicpc.net/problem/1759

Explain

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며, 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다.
암호를 이루는 알파벳은 오름차순 정렬
암호로 사용할 수 있는 문자의 종류는 C가지

Key Point

알파벳을 입력받은 다음

1. 오름차순 정렬을 먼저 한다.
2. 각각의 문자를 사용할지 말지 결정한다.

go(L, alphabet, password, index)

• L : 만들어야 하는 암호의 길이
• alphabet : 사용할 수 있는 알파벳 배열
• password : 현재까지 만든 암호
• index : 사용할 지 말 지 결정해야 하는 알파벳의 index

예외

1. 불가능한 경우 : 더 이상 사용할 알파벳 배열이 없을 경우
2. 정답을 찾은 경우 : 지금까지 만든 암호의 길이가 만들어야 하는 암호의 길이와 같을 경우
3. 다음 경우

• i번째 알파벳을 사용하는 경우 = go(L, alphabet, password+alphabet[index], index+1)
• i번째 알파벳을 사용하지 않는 경우 = go(L, alphabet, password, index+1)

Code

public class Exam1759 {
	// 자음과 모음의 개수를 check하는 배열
	public static boolean check(String password) {
		int ja = 0; // 자음
		int mo = 0; // 모음
		
		for(char word : password.toCharArray()) {
			// 문자열의 문자 각각이 자음인지 모음인지 확인하기 위한 과정
			if(word == 'a' || word == 'e' || word == 'i' || word == 'o' || word == 'u') { 
				mo++;
			}else {
				ja++;
			}
		}
		return ja>=2 && mo>=1;
	}
	
	// 재귀 함수
	public static void go(int L, String[] alphabet, String password, int index) {

		// 정답을 찾은 경우
		
		if(L == password.length()) {
			if(check(password)) {
				System.out.println(password);
			}
			return;
		}
		
		// 더 이상 사용할 알파벳이 없을 경우 [다 탐색을 진행한 경우]
		
		if(index >= alphabet.length) {
			return;
		}
		
		go(L, alphabet, password+alphabet[index], index+1); // 다음의 알파벳을 사용하는 경우 [ 현재까지 만든 암호에 다음 알파벳을 이어 붙여준다.] 그리고 index 증가
		go(L, alphabet, password, index+1); // 다음의 알파벳을 사용하지 않는 경우 [다음 알파벳을 사용하지 않으므로 현재까지 만든 암호만 넘겨준다.] 그리고 수행을 했으므로 index 증가
		// ( 다음 알파벳은 사용하지 않았지만, 다 다음 알파벳에 대해서 진행해야 하기 때문에 index를 증가시키는 것이다. )
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(bf.readLine(), " ");
		int L = Integer.parseInt(st1.nextToken()); // 만들어야 하는 암호의 길이 : 4
		int C = Integer.parseInt(st1.nextToken()); // 암호로 사용할 수 있는 문자의 종류 : 6가지
		
		String[] alphabet = new String[C];
		StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");
		for(int i=0;i<C;i++) {
			alphabet[i] = st2.nextToken();
		}
		
		Arrays.sort(alphabet); // 오름차순으로 정렬
		
		go(L, alphabet, "", 0);
	}
}