BOJ) 암호 만들기

암호 만들기

1759번: 암호 만들기

풀이

 

C 개의 문자 중 L개를 선택해서 만들 수 있는 암호를 출력하는 문제다.

이 때, 암호는 모음(a,e,i,o,u)이 최소 하나 이상 자음이 두개 이상인 조합만 가능하다.

또한, 모든 암호의 경우를 사전순서대로 출력해야한다.

 

위의 두 조건을 충족하기 위해

C개 중 L개를 선택하는 것은 DFS를, 사전 순서대로 하기 위해 정렬을 선택했다.

DFS이후에 정렬을 하기에는 너무 많은 시간과 메모리를 낭비할 것 같아서 입력 받자마자 정렬을 해주었다.

 

DFS에서는 index에 따라서 해당 글자가 모음인지 자음인지에 따라 각각 갯수를 세주면서 글자를 담았다.

재귀 호출 도중에 자음과 모음으로 이루어진 비밀번호 조합이 L개가 된다면, return해주었다.

이 때, 모임이 최소 하나 이상이면서 자음이 두개 이상인지 확인하고, 맞으면 답을 출력할 StringBuffer에 append해줬다.

 

코드1

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    final static String[] vowelArr = {"a","e","i","o","u"};
    final static String NEWLINE = "\n";
    final static int MIN_VOWEL =1, MIN_CONSONANT=2;
    static int l,r;
    static String[] wordArr;
    static StringBuffer sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        wordArr = br.readLine().split(" ");
        Arrays.sort(wordArr);
        br.close();
        solution();
    }

    private static void solution() {
        LinkedList<String> passList = new LinkedList<>();
        sb = new StringBuffer();
        dfs(0,0,0,passList);
        System.out.println(sb.toString());
    }

    private static void dfs(int idx, int vowel, int consonant, LinkedList<String> passList) {
        if(vowel+consonant == l) {
            if(vowel >= MIN_VOWEL && consonant >= MIN_CONSONANT) {
                for (String str : passList) {
                    sb.append(str);
                }
                sb.append(NEWLINE);
            }
            return;
        }
        if(idx == r) {
            return;
        }

        for(int i=idx; i<r; i++) {
            String now = wordArr[i];
            passList.offer(now);
            if(now.equals(vowelArr[0]) || now.equals(vowelArr[1]) || now.equals(vowelArr[2]) || now.equals(vowelArr[3]) || now.equals(vowelArr[4])) {
                dfs(i+1, vowel+1, consonant, passList);
            } else {
                dfs(i+1, vowel, consonant+1, passList);
            }
            passList.pollLast();
        }
    }
}