[백준] 암호 만들기 1759 - JAVA

문제

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

1759번: 암호 만들기

풀이

문자들의 조합으로 단어를 만들면 된다. 따라서 백트레킹을 이용한다.

오름차순으로 단어를 만들어야 되기 때문에 백트레킹 전에 오름차순으로 정렬한다.

그리고 그 전의 문자와 현재 문자를 비교하여 오름차순이면 백트레킹을 시행하고 아니면 그 다음 문자로 넘어간다. 

이때 단어안에 모음은 최소 1개, 자음은 최소 2개가 필요하다. 따라서, 전역변수 2개를 선언한 다음 모음일 경우 변수 1개의 값을 증가시기고 자음일 경우 변수 1개의 값을 증가시키면 된다.

 

코드

import java.io.*;
import java.util.*;

public class Main {	 
	
	static int L, C;
	static char arr[];
	static StringBuilder sb = new StringBuilder();
	static boolean check[];
	static int aeiou = 0;
	static int others = 0;
	
	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());
		
		arr = new char [C];
		check = new boolean[C];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<C;i++) {
			arr[i] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(arr);
		
		back(1, "");
		
		System.out.println(sb);
	}
	
	static void back(int idx, String str) {
		if(idx == L+1) {
			if(aeiou >= 1 && others >=2)
				sb.append(str).append("\n");
			return;
		}
		for(int i=0;i<C;i++) {
			if(check[i]) continue;
			if(idx > 1 && str.charAt(str.length()-1) > arr[i]) continue;
			check[i] = true;
			if(arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
				aeiou++;
			else
				others++;
			back(idx+1, str+arr[i]);
			if(arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
				aeiou--;
			else
				others--;
			check[i] = false;
		}
	}
}