BOJ - 암호 만들기

 

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

1759번: 암호 만들기

 

• 백트랙킹을 이용하여 규칙에 맞는 암호문을 만들어 내는 문제이다.
• 최적화는 비트마스킹을 활용했다.
• Java String => 248ms
• 비트마스킹 => 140ms
• 코드는 비트마스킹 풀이법이다.

 

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder builder = new StringBuilder();

    private static int L;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        char[] tokens = new char[C];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < tokens.length; i++) {
            tokens[i] = st.nextToken().charAt(0);
        }

        Arrays.sort(tokens);
        //한개의 모음, 두개의 자음, 증가하는 순서
        char[] crypto = new char[L];
        dp(0, tokens, 0, 0, 0, crypto);
        System.out.println(builder);
    }

    private static void dp(int mask, char[] tokens, int depth, int numOfVowels, int numOfCons, char[] crypto) {
        if (depth == L) {
            //한개의 모음, 두개의 자음 체크
            if (numOfVowels >= 1 && numOfCons >= 2) {
                builder.append(new String(crypto) + "\n");
            }
            return;
        }

        for (int i = 0; i < tokens.length; i++) {
            if ((mask & (1 << tokens[i])) == 0) {
                //증가하는 순서일 경우 
                if (depth > 0 && crypto[depth - 1] > tokens[i]) continue;

                crypto[depth] = tokens[i];
                if (tokens[i] == 'a' || tokens[i] == 'e' || tokens[i] == 'u' || tokens[i] == 'i' || tokens[i] == 'o') {
                    dp(mask | (1 << tokens[i]), tokens, depth + 1, numOfVowels + 1, numOfCons, crypto);
                } else {
                    dp(mask | (1 << tokens[i]), tokens, depth + 1, numOfVowels, numOfCons + 1, crypto);
                }
            }
        }
    }
}