[JAVA] 백준 1759 - 암호만들기

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

n개의 알파벳이 주어졌을 때, 사전 오름차순이며 모음(a,e,i,o,u) 최소 1개, 자음 두개로 이루어진 암호의 개수를 구하는 문제이다.

 

먼저 입력으로 받은 알파벳 배열을 정렬 후 자음, 모음으로 나누고 dfs로 완전탐색한 문자열의 길이가 L에 도달하면 모음개수, 자음개수 조건을 통과한 문자열에 대해 우선순위큐에 넣고 출력했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class Main {
    static PriorityQueue<String> str = new PriorityQueue<>();
    static List<String> must = new ArrayList<>();
    static List<String> notMust = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        String[] arr = br.readLine().split(" ");
        must = Arrays.stream(arr).filter(x -> x.equals("a")||x.equals("i")||x.equals("o")||x.equals("e")||x.equals("u")).collect(Collectors.toUnmodifiableList());
        notMust = Arrays.stream(arr).filter(x -> !x.equals("a")&&!x.equals("i")&&!x.equals("o")&&!x.equals("e")&&!x.equals("u")).collect(Collectors.toUnmodifiableList());
        Arrays.sort(arr);
        for(int i = 0; i<arr.length; i++){
            recursion(i,arr[i],info[0],1,arr,must.contains(arr[i])?1:0,notMust.contains(arr[i])?1:0);
        }
        while(!str.isEmpty()){
            System.out.println(str.poll());
        }
    }

    static void recursion(int idx, String s, int target, int now, String[] arr, int mustCount, int notMustCount){
        if(now==target){
            if(mustCount>=1&&notMustCount>=2)str.offer(s);
            return;
        }
        for(int i = idx+1; i<arr.length; i++){
            recursion(i, s.concat(arr[i]), target,now+1,arr,must.contains(arr[i])?mustCount+1:mustCount,notMust.contains(arr[i])?notMustCount+1:notMustCount);
        }
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}