문제링크

풀이

바킹독 백트래킹 문제집의 N과 M 시리즈를 먼저 풀고 이 문제를 풀이하면 쉽게 풀이할 수 있다.

N과 M 시리즈처럼 기본적인 백트래킹 알고리즘을 풀이하되, 암호가 모음 최소 1개, 자음 최소 2개 사용되었다는 조건을 만족할 때만 출력해주면 된다.
그리고 암호는 증가하는 순서 즉, 오름차순으로 정렬되어있기 때문에 백트래킹 메서드에서 이전에 사용한 알파벳의 인덱스를 넘겨줘서 이전에 사용한 알파벳 이후의 인덱스만 사용하도록 해야한다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol1759 {
    static int l, c;
    static String[] str, pwd;
    static String[] vowels = {"a", "e", "i", "o", "u"};
    static int vowelsCnt = 0, consonantsCnt = 0;
    static boolean[] isUsed = new boolean[16];
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        str = new String[c];
        pwd = new String[l];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < c; i++) {
            str[i] = st.nextToken();
        }
        Arrays.sort(str);
        backtracking(0,0);
        bw.flush();
        bw.close();
    }

    public static void backtracking(int start, int depth) throws Exception {
        if (depth == l) {
            if (vowelsCnt >= 1 && consonantsCnt >= 2) { //  모음, 자음 개수가 문제의 조건에 맞을 때만 출력
                for (int i = 0; i < depth; i++) {
                    bw.write(pwd[i]);
                }
                bw.write("\n");
            }
            return;
        }
        for (int i = start; i < c; i++) {
            if (!isUsed[i]) {
                int isVowels = Arrays.binarySearch(vowels, str[i]); //  다음 사용할 문자가 모음인지 확인
                if (isVowels >= 0) {
                    vowelsCnt++;
                } else {
                    consonantsCnt++;
                }
                pwd[depth] = str[i];
                isUsed[i] = true;
                backtracking(i + 1, depth + 1); //  사용한 알파벳의 인덱스를 넘겨준다. 
                if (isVowels >= 0) {
                    vowelsCnt--;
                } else {
                    consonantsCnt--;
                }
                isUsed[i] = false;
            }
        }

    }
}

코드2

코드가 좀 지저분한 거 같아서 GPT에게 수정을 부탁했더니 매우 깔끔하게 수정되었다.
수정된 부분은 다음과 같다.

• start 변수를 이용해서 이미 사용된 문자를 건너뛰기 때문에 isUsed 불필요
• 그냥 떠오르는데로 사용한 binarySearch를 Set을 사용해서 직관적으로 변경
• 모음/자음 개수를 전역변수로 관리하지 않고 백트래킹 메서드의 매개변수로 넘겨줌

package BOJ;

import java.io.*;
import java.util.*;

public class sol1759 {
    static int l, c;
    static String[] str, pwd;
    static final Set<String> vowels = Set.of("a", "e", "i", "o", "u");
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        str = new String[c];
        pwd = new String[l];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < c; i++) {
            str[i] = st.nextToken();
        }

        Arrays.sort(str);
        backtracking(0, 0, 0, 0);
        bw.flush();
        bw.close();
    }

    // start: 현재 인덱스 시작점
    // depth: 현재 몇 개 골랐는지
    // vowelCnt: 지금까지 선택한 모음 개수
    // consonantCnt: 지금까지 선택한 자음 개수
    public static void backtracking(int start, int depth, int vowelCnt, int consonantCnt) throws Exception {
        if (depth == l) {
            if (vowelCnt >= 1 && consonantCnt >= 2) {
                for (int i = 0; i < l; i++) {
                    bw.write(pwd[i]);
                }
                bw.newLine();
            }
            return;
        }

        for (int i = start; i < c; i++) {
            String ch = str[i];
            pwd[depth] = ch;

            if (vowels.contains(ch)) {
                backtracking(i + 1, depth + 1, vowelCnt + 1, consonantCnt);
            } else {
                backtracking(i + 1, depth + 1, vowelCnt, consonantCnt + 1);
            }
        }
    }
}