[백준] 1759번 암호 만들기 풀어보기 [Java]

조합 문제였다. 암호 조합들은 알파벳 순으로 출력을 해야된다. 암호는 모음이 최소 한개, 자음이 최소 두개로 구성되어야 했다.

 

👨‍🏫  풀이

들어온 알파벳들을 오름차순으로 정렬을 해주었다.

그리고 조합을 돌렸다.

모음은 1개 이상, 암호의 길이 - 2 이하이여만 했다. 그래서 해당 조건을 만족하는 암호를 출력하도록 했다.

알파벳을 오름차순으로 정렬을 해놓고, 조합을 돌렸기 때문에 암호들이 알파벳 순으로 출력되도록 풀 수 있다.

 

👨🏻‍💻 코드 

package 번1759;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    static int minM, maxM;
    static String[] alphabets;
    static String[] vowels = {"a", "e", "i", "o", "u"};
    static int L, C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(i -> Integer.parseInt(i)).toArray();
        L = input[0]; C = input[1];
        minM = 1; maxM = L - 2;
        alphabets = br.readLine().split(" ");
        Arrays.sort(alphabets);
        dfs(0, 0, new Stack<String>());
    }

    static void dfs(int idx, int curM, Stack<String> cur){
        if(curM >= minM && curM <= maxM && cur.size() == L){
            printResult(cur);
        } else{
            for(int i = idx ; i < C ; i++){
                if(curM > maxM || (curM == maxM && isVowel(i))) continue;
                int nextM = curM;
                if(isVowel(i)) nextM++;
                cur.push(alphabets[i]);
                dfs(i + 1, nextM, cur);
                cur.pop();
            }
        }

    }

    private static boolean isVowel(int i) {
        for (String vowel : vowels) {
            if (vowel.equals(alphabets[i])) {
                return true;
            }
        }
        return false;
    }


    private static void printResult(Stack<String> cur) {
        String print = "";
        for (String s : cur) {
            print += s;
        }
        System.out.println(print);
    }
}