[백준] 암호만들기

진짜 오랜만에 알고리즘을 풀었다.

완전탐색으로 해결할 수 있는 간단한 문제였으나, 조합이 순간 기억이 안 나 조금 헤멨다.

 

모음이 1개, 자음이 2개 이상 무조건 들어가야 하는 조건을 충족시키기 위해 set의 contains를 통해 시간복잡도를 줄였다.

조합에서는 C가 15 이하라는 조건이 있어 비트마스킹을 통해 시간복잡도를 줄일 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int l, c;
    static List<String> arr, ans;
    static Set<Character> ms;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        ms = Set.of('a', 'e', 'i', 'o', 'u');
        arr = new ArrayList<>();
        ans = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < c; i++) {
            String str = st.nextToken();
            arr.add(str);
        }

        comb(-1, 0, 0);

        Collections.sort(ans);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < ans.size(); i++) {
            sb.append(ans.get(i)).append("\n");
        }

        System.out.println(sb);
    }

    public static void comb(int idx, int cnt, int selected) {
        if(cnt == l) {
            cal(selected);
            return;
        }

        for(int i = idx + 1; i < c; i++) {
            comb(i, cnt + 1, selected | (1 << i));
        }
    }

    public static void cal(int selected) {
        int sum = 0;

        for(int i = 0; i < c; i++) {
            if((selected & (1 << i)) > 0) {
                String str = arr.get(i);
                if(ms.contains(str.charAt(0))) {
                    sum += 100;
                } else {
                    sum += 1;
                }
            }
        }

        if(sum < 100 || sum % 100 < 2) {
            return;
        }

        List<String> temp = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < c; i++) {
            if((selected & (1 << i)) > 0) {
                String str = arr.get(i);
                temp.add(str);
            }
        }

        Collections.sort(temp);
        for(String s : temp) {
            sb.append(s);
        }

        ans.add(sb.toString());
    }

}