[백준] 1795번 암호 만들기 java

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

문제 풀이 :

백 트래킹을 이용합니다.

주어진 문자 종류 C 가지에서 서로 다른 L개의 알파벳으로 암호를 구하는데 조건을 해결하기 위해서는

1. 문자열을 담은 배열을 정렬 시킵니다.

2. 문자열을 L개 만큼 조합합니다.

3.1 이 때 최소 한 개의 모음과 최소 두개의 자음으로 구성되면 출력해줍니다.

3.2 아니라면 왔던 길을 다시 되돌아가서 새롭게 암호를 조합합니다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int L,C;
	static String[] arr;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		L = sc.nextInt();
		C = sc.nextInt();
		arr = new String[C];
		for (int i = 0; i < C; i++) {
			arr[i] = sc.next();
		}
		//1. 정렬
		Arrays.sort(arr);

		comb(0,"");
	}
	//2. 최소 모음 1개, 자음 2개
	public static void comb(int index, String s) {
		if(s.length()==L) {//길이가 L개 이고
			if(check(s))//모음 1개, 자음 2개이면 출력한다
				System.out.println(s);
			return;
		}
		
		if(index>=C) return;//arr 배열을 다 돌면 종료
		
		comb(index+1,s+arr[index]);//해당 문자를 포함 시켜 암호를 만든경우
		comb(index+1,s);
	}
	public static boolean check(String s) {
		int mo = 0, ja = 0;
		
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
				mo++;
			else
				ja++;
		}
		return mo>=1 && ja>=2;
	}
	
}