[BOJ] 1759: 암호 만들기 (JAVA)

문제

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

 

풀이

문제에서 주어지는 조건은 다음과 같다.

• 주어지는 알파벳의 개수가 최대 15개 ⇒ 완전탐색?
• 주어지는 L개의 알파벳 중에 C개의 알파벳을 중복없이 고르기 ⇒ 순열? 조합?
• 암호를 이루는 알파벳을 증가하는 순서대로 배열하기 ⇒ 입력받은 알파벳을 정렬하기
• 암호는 최소 1개의 모음, 최소 2개의 자음으로 구성하기 ⇒ 가능성이 있는 암호인지 확인하기 위해 모음의 개수와 자음의 개수 세기

a b c는 암호가 될 수 있지만 b a c는 암호가 될 수 없다. 이는 순서가 있는 것처럼 보여, 순열로 풀어야 한다고 생각할 수 있다. 하지만 알파벳이 정렬된 상태에서 고르는 것이므로, 현재 알파벳의 앞부분을 확인하지 않는다. 따라서 조합을 사용하면 된다.

 

 

또한 암호를 이루는 알파벳을 선택할 때, 가능성이 있는 암호인지 확인하기 위해 모음의 개수와 자음의 개수를 세야 한다. 길이가 C인 암호를 만들었을 때, 모음이 1개 이상이고 자음이 2개 이상이면 해당 암호를 출력하면 된다.

 

코드

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

public class BOJ_1759 {

	static int L, C;
	static char[] chars, result;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken()); // 암호 길이
		C = Integer.parseInt(st.nextToken()); // 가능한 알파벳 개수
		chars = new char[C]; // 알파벳 저장용
		result = new char[L]; // 암호 저장용
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			chars[i] = st.nextToken().charAt(0);
		}
		// 알파벳 정렬
		Arrays.sort(chars);
		dfs(0, 0, 0, 0);
		System.out.println(sb);
	}

	// C개 중에 L개 뽑기 (조합)
	static void dfs(int depth, int start, int a, int b) { // a: 모음의 수, b: 자음의 수
		if (depth == L) {
			// 암호는 최소 1개의 모음, 최소 2개의 자음으로 구성됨
			if (a >= 1 && b >= 2) {
				for (char c : result) {
					sb.append(c);
				}
				sb.append("\n");
			}
			return;
		}

		for (int i = start; i < C; i++) {
			result[depth] = chars[i];
			if (checkChar(chars[i]))
				dfs(depth + 1, i + 1, a + 1, b);
			else
				dfs(depth + 1, i + 1, a, b + 1);
		}
	}

	static boolean checkChar(char c) {
		if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
			return true;
		return false;
	}
}

 

후기

처음에 암호의 조건이 최소 1개의 모음, 최소 2개의 자음을 사용해야 한다는 것을 흘려봤다.. 그리고 암호를 저장하는 배열의 길이를 잘못 초기화했다ㅎ..

 

이런 쓸데없는 실수들이 반복되지 않도록 꼼꼼히 문제를 풀도록 하자.

---