boj 1759 암호 만들기

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

1759번: 암호 만들기

간단한 백트래킹 문제입니다.

 

출력이 오름차순이므로 입력으로 주어지는 알파벳을 오름차순으로 먼저 정렬해줍니다.

그 다음 재귀를 통해 알파벳을 추가할 때마다 모음인지 자음인지 확인하여 갯수를 갱신시켜주면서 재귀를 돌려줍니다.

가능한 암호조합을 모두 찾아낸 후에 이 조합이 모음 1개, 자음 2개 이상을 포함하고 있는 경우에만 출력합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static char list[] = new char[16];
    static int L, C, a, b;
 
    static void func(int idx, int cnt, String str) {
        if (cnt == L) {
            if (a < 1 || b < 2)
                return;
            sb.append(str).append("\n");
            return;
        }
 
        if (idx >= C)
            return;
 
        for (int i = idx; i < C; i++) {
            if (list[i] == 'a' || list[i] == 'e' || list[i] == 'i' || list[i] == 'o' || list[i] == 'u')
                a++;
            else
                b++;
 
            func(i + 1, cnt + 1, str + list[i]);
 
            if (list[i] == 'a' || list[i] == 'e' || list[i] == 'i' || list[i] == 'o' || list[i] == 'u')
                a--;
            else
                b--;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            list[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(list, 0, C);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0, "");
        System.out.print(sb.toString());
    }
}