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

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

1759번: 암호 만들기

 

백트래킹으로 DFS를 응용했다.

 

조합으로 길이가 L인, 최소 한 개의 모음과 최소 두 개의 자음이 포함된 암호를 만든다. 

 

시간제한이 넉넉했기 때문에 한 암호를 만들고 모음이 한 개 이상이고 자음이 두 개 이상인지 체크했다. 

 

public class Main {
    static int L;
    static int C;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/P1759/input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        ArrayList<Character> arr = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=C; i++){
            arr.add(st.nextToken().charAt(0));
        }
        Collections.sort(arr); // 사전순 정렬

        for(int i=0; i<arr.size(); i++){
            StringBuilder sb = new StringBuilder();
            sb.append(arr.get(i));
            DFS(i, arr, sb);
        }
    }

    public static void DFS(int index, ArrayList<Character> arr, StringBuilder sb){
        if(sb.length()==L){
            int l = 0, r = 0;
            for(char c:sb.toString().toCharArray()){
                if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') l++;
                else r++;
            }
			// 자음, 모음 개수 체크 
            if(l>=1 && r>=2) System.out.println(sb.toString());
            return;
        }
        for(int i=index+1; i<arr.size(); i++){
            sb.append(arr.get(i));
            DFS(i, arr, sb);
            sb.deleteCharAt(sb.length()-1);
        }

    }
 }