BOJ 1759 - 암호 만들기

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

1759번: 암호 만들기

 

아이디어

일단 먼저 최소 한개의 모음과 최소 두 개의 자음이라는 조건을 제외하고 생각해보자

 

서로 다른 C개의 알파벳 소문자들 중 L개를 중복없이 사전순으로 순서있게 나열하는 순열 문제이다. 

C개의 알파벳을 먼저 정렬한 후 중복없이 사전순으로 조합을 짜기 위해 prev 인자를 통해 k자리의 다음 자리인 k+1 자리는 prev +1 부터 탐색하도록 설정해서 완전 탐색으로 모든 경우의 수를 구한다. 

 

이제 여기서 완성된 가능한 모든 암호 조합의 모음 개수와 자음 개수를 세서 조건에 맞을 경우에만 출력시켜준다.

 

아 이거 설명하듯이 풀이를 글로 써볼라니까 어렵네.. 내가 쓴 설명이 무슨 말인지 알아듣는 사람..?

인생 최초 골드문제 풀이없이 혼자 품 

 

시간복잡도

시간 복잡도가 순열의 경우 O(nPm)으로 알고 있는데 N과 M-1의 최댓값은 15이니까 15! / (15-15)! = 15!이라서 

무조건 2초 초과인데 

 

여기선 아마 조건으로 사전순인 경우만 탐색하게 해서 시간복잡도가 많이 줄어든듯..? 확실하진 않음.. 일단 124ms로 빠르게 통과는 함..

 

 

구현

 

import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static char[] alphabet, selected;
    static HashSet<Character> vowels = new HashSet<>();

    public static void main(String[] args) throws IOException {
        init();

        rec_func(1, 0);

        bw.close();
    }

    private static void rec_func(int k, int prev) throws IOException {
        if (k == M + 1) {

            // 모음, 자음 조건 체크
            int cnt_v = 0;
            int cnt_c = 0;

            for (int i = 1; i <= M; i++) {
                if (vowels.contains(selected[i])) {
                    cnt_v++;
                } else {
                    cnt_c++;
                }
            }

            // 조건 통과시에만 출력
            if (cnt_v >= 1 && cnt_c >= 2) {
                for (int i = 1; i <= M; i++) {
                    bw.write(selected[i]);
                }
                bw.write("\n");
            }

        } else {
            for (int i = prev + 1; i <= N; i++) {
                char a = alphabet[i];
                selected[k] = a;

                rec_func(k + 1, i);

                selected[k] = 0;
            }
        }
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        alphabet = new char[N + 1];
        selected = new char[M + 1];

        // 모음 set
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');


        // String -> Char
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            alphabet[i] = st.nextToken().charAt(0);
        }

        // 사전순 정렬
        Arrays.sort(alphabet);
    }

}