[BOJ] - 암호 만들기 / 1759번 (Java)

[BOJ] - 암호 만들기 / 1759번 (Java)

[BOJ] - 암호 만들기 / 1759번 (Java)

1. 문제 접근

C개의 문자들이 주어질 때, L개의 문자로 이루어진 암호 문자열을 만들면 된다.

 

이 때, 1개 이상의 모음, 2개 이상의 자음이 포함되어야하며, 암호문은 반드시 증가하는 순서로 배열되어있다는 것이다.

 

일반적인 조합(Combination)문제에 대해 약간의 추가적인 조건들이 추가된 문제라고 생각한다.

 

`암호문은 반드시 증가하는 순서로 배열`라는 조건을 이용하여 조합을 구성하기 전에 주어진 문자 배열을 오름차순으로 정렬해야한다.

 

또한 기저조건(`selectIdx == L`)을 만족할 경우, 추가적으로 L개의 문자열을 조회하며 모음, 자음의 개수가 조건을 만족하는지 여부를 확인해야한다.

 

---

2. 코드

package boj;

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

/**
 * [BOJ] - 암호 만들기 / 1759번 
 * @author JinHxxxxKim
 * 
 * 1. 두 정수 L, C를 입력받는다.
 * 		- L: 암호문의 길이
 * 		- C: 주어진 알파벳의 수
 * 2. C개의 문자들을 입력받는다.
 * 3. 주어진 문자들을 오름차순으로 정렬한다.
 * 4. 조합을 구성한다.
 * 		- 기저조건: selectIdx == L
 * 			- 자음, 모음의 수가 충족되지 않으면 append하지 않는다.
 */
public class Sol_1759 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static int L, C;
	private static char[] alphabet;
	private static int[] select;
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		alphabet = new char[C];
		
		st = new StringTokenizer(br.readLine().trim());
		for (int idx = 0; idx < C; ++idx) {
			alphabet[idx] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(alphabet);
		select = new int[L];
		makeCrypto(0, 0);
		System.out.println(sb);
	}

	private static void makeCrypto(int selectIdx, int elementIdx) {
		// 기저조건
		if(selectIdx == L) {
			// 자음 모음 카운팅
			int gatherCnt = 0;
			int consonantCnt = 0;
			for (int idx = 0; idx < L; ++idx) {
				if (alphabet[select[idx]] == 'a' 
					|| alphabet[select[idx]] == 'e' 
					|| alphabet[select[idx]] == 'i' 
					|| alphabet[select[idx]] == 'o'
					|| alphabet[select[idx]] == 'u')
					gatherCnt++;
				else
					consonantCnt++;
			}
			if (gatherCnt > 0 && consonantCnt > 1) {
				for (int idx = 0; idx < L; ++idx) {
					sb.append(alphabet[select[idx]]);
				}
				sb.append("\n");
			}
			return;
		}
		if(elementIdx == C) {
			return;
		}
		
		select[selectIdx] = elementIdx;
		makeCrypto(selectIdx+1, elementIdx + 1);
		makeCrypto(selectIdx, elementIdx + 1);
	}
}

---

3. 디버깅

`select[]`배열에 저장되어있는 값은 `alphabet[]`배열에 대한 인덱스 값이다.

 

따라서 기저조건에서 자음, 모음 판별 또는 `StringBuilder`에 `append()`할 때,  `alphabet[idx]`로 접근하는 것이 아닌, `alphabet[select[idx]]`와 같이 접근해야 한다.

---

4. 결과