암호 만들기

📍 문제 설명

 

💡 접근

시간초과 판정이 나서 이것저것 해봤는데, 최종 문제는 순열로 풀었다는 것이다.

오름차순 정렬을 순열을 뽑고나서 진행하는게 아니라 정렬 먼저 한 다음 조합으로 뽑아내면된다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k;
    static int[][] board,dis;
    static int[] ch;
    static String[] split,pm;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[] combi;
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        kb.nextLine();
        split = new String[m];
        split = kb.nextLine().split(" ");
        ch = new int[m];
        pm = new String[n];
        //6개중에 4개를 뽑는 조합문제?
        //오름차순정렬 시키면 조합으로 풀 수 있음
        Arrays.sort(split);
        T.solution(0,0);
        Collections.sort(list);
        StringBuffer sb = new StringBuffer();
        for(String s : list) sb.append(s + "\n");
        System.out.println(sb);
    }

    private void solution(int L, int s) {
        //암호가 완성되면
        if(L == n) {
            int moemCnt = 0, jaemCnt = 0;
            //최소 1개의 모음과 2개의 자음이 있어야함 그리고 오름차순 되어있어야함
            for(int i = 0; i < pm.length; i++) {
                boolean flag = false;
                if(pm[i].equals("a") || pm[i].equals("e") || pm[i].equals("i") || pm[i].equals("o") || pm[i].equals("u")) {
                    flag = true;
                }
                if(flag) moemCnt++;
                else jaemCnt++;
                if(moemCnt >= 1 && jaemCnt >= 2) break;
            }

            StringBuffer tmp = new StringBuffer();

            if(moemCnt >= 1 && jaemCnt >= 2) {
                for(String str : pm) {
                     tmp.append(str);
                }
                list.add(String.valueOf(tmp));
            }
        }
        else {
            //m가닥으로 뻗어나간다.
            for(int i = s; i < m; i++) {
                pm[L] = split[i];
                solution(L+1, i+1);
            }
        }
    }
}