[백준](Java) 1759 - 암호 만들기

문제 링크

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

문제 풀이

메모리 초과가 떠서 한 3일은 고민하다가 결국엔 다른 사람의 풀이를 슥 보고 비슷하게 접근해서 풀었다. 부족했던 부분은
1) 암호 배열을 먼저 오름차순으로 정렬한뒤 dfs를 돌릴것
2) dfs 부분에서 for문의 i값을 0이 아닌 idx로 해야지 현재값보다 작은 idx에 있는 값을 가져오지 않는다.
3) idx를 종료조건으로 사용하게 될경우, 암호 배열의 길이를 끝까지 담을수 없게되므로
다른 변수(cnt)를 사용해서 현재의 idx를 나타내는 변수와, 길이를 나타내는 변수 2개를 dfs의 인자로 넘겨준다.

코드

import java.util.*;

public class Main {

    static int n;
    static int m;
    static String[] arr;
    static PriorityQueue<String> pq;
    static PriorityQueue<String> temp;
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        arr = new String[m];
        pq = new PriorityQueue<>();
        temp = new PriorityQueue<>();
        boolean [] chk = new boolean[m];


        for (int i = 0; i < m; i++) {
            arr[i] = sc.next();
        }

        Arrays.sort(arr);
        //System.out.println(Arrays.toString(arr));
        dfs( 0,0,chk);
    }


    public static void dfs(int cnt, int idx, boolean [] chk) {
        //System.out.println(idx+" "+Arrays.toString(chk));
        if (cnt == n) {
            if (possible(chk)) {
                //System.out.println(Arrays.toString(chk));
                for(int i=0; i<m; i++){
                    if(chk[i]){
                        System.out.print(arr[i]);
                    }
                }
                System.out.println("");
            }
            return;
        }

        for (int i = idx; i < m; i++) {
            if (chk[i]) {
                continue;
            }
            chk[i] = true;
            dfs(cnt+1,i+1, chk);
            //System.out.println("=============");
            chk[i] = false;
        }
    }

    public static boolean possible(boolean [] chk){
        int mcnt = 0;
        int jcnt =0;
        for(int i=0; i<chk.length; i++){
            if(chk[i]){
                if ((arr[i]).equals("a") || (arr[i]).equals("e") || (arr[i]).equals("i") || (arr[i]).equals("o") || (arr[i]).equals("u")) {
                    mcnt++;
                } else {
                    jcnt++;
                }
            }
        }

       return mcnt>=1 && jcnt>=2 ? true : false;
    }
}