🔗 Problem

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

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

// 암호 만들기

public class BJ1759 {
	
	static int L;
	static int C;
	static char[] arr;
	static int length;
	static char[] output;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new char[C];
		output = new char[L];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < C; i++) {
			arr[i] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(arr);
		backTracking(0, 0);
	}
	
	private static void backTracking(int length, int idx) {
		
		if(length == L) {
			if(isValid()) {
				System.out.println(output);
				return;
			}
		}
		
		if(idx >= arr.length || length >= output.length) return;
		
		for(int i = idx; i < C; i++) {		// idx부터 시작하므로 현위치보다 작은 알파벳은 탐색 제외
			output[length] = arr[i];	
			backTracking(length+1, i+1);
		}

	}
	
	private static boolean isValid() {
		
		int vowel = 0;
		int cons = 0;
		
		for(int i = 0; i < output.length; i++) {
			if(output[i] == 'a' || output[i] == 'e' || output[i] == 'i' || output[i] == 'o' || output[i] == 'u') {
				vowel++;
			}
			else cons++;
			
			if(vowel >= 1 && cons >= 2) return true;
		}
		return false;
	}

}

💡 Learned

아이디어

• 처음에는 idx부터 for문을 돌릴 생각을 못하고 isPromising() 함수를 따로 만들어서 너무 복잡해졌다.
• Back tracking 알고리즘을 사용할 때, 빈 root node에서부터 각 node를 탐색해야 하기 때문에 depth = 0으로 시작한다.

런타임 에러 발생

• ArrayIndexOutOfBounds: backTracking()에서 if(length == L)을 만족하지 못하면 length가 계속 증가하기 때문에 output[length]에서 인덱스 범위를 초과할 수 있다.