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

 

 

 

백트래킹으로 풀 수 있는 문제이다.

 

조건은, 모음이 1개 이상 / 자음이 2개 이상이다.

암호의 문자는 하나씩밖에 사용할 수 없으니 백트래킹 함수는 인자를 두 개 받도록 설정해 처리해주자.

 

값의 후보가 되는 요소들은 리스트로 담아서 풀 수 있는데, 이번에는 배열을 사용해서 풀어보자.

 

arr의 값이 cand의 인덱스로 접근해서 답을 출력한다.

 

 

 

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

		public class Main {	

			static int L, C = 0;
			static int[] arr;
			static char[] cand;  
			
			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());

				cand = new char[C];
				arr = new int[15];

				st = new StringTokenizer(br.readLine());

				for(int i=0; i<C; i++){
					cand[i] = st.nextToken().charAt(0);
				}

				Arrays.sort(cand);

				solve(0,0);
				
			}

			static void solve(int k, int start){
				if(k == L){
					boolean chk = false;		
					int cnt1 = 0;
					int cnt2 = 0;

					for(int i =0; i<L; i++){
						if(cand[arr[i]] == 'a' || cand[arr[i]] == 'e' || cand[arr[i]] == 'i' || cand[arr[i]] == 'o' || cand[arr[i]] == 'u'){
							cnt1++;
						}else{
							cnt2++;
						}
					}

					if(cnt1 >= 1 && cnt2 >= 2){
						chk = true;
					}

					if(chk){
						for(int i=0; i<L; i++){
							System.out.print(cand[arr[i]]);
						}
						System.out.println();
					}
					return;
				}	
				
				// used필요없음 어차피 하나씩 증가하면서.. 			

				for(int i = start; i<C; i++){
					arr[k] = i;
					solve(k+1, i+1);
				}
			}

		}