문제 : 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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);
}
}