백준_1759_암호만들기

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

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

public class Main {
    static int L;
    static int C;
    static char[] chars;
    static boolean[] isSelected;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        chars = new char[C];
        isSelected = new boolean[C];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            chars[i] = st.nextToken().charAt(0); // 첫번째 문자를 추출
        }
        //정렬
        Arrays.sort(chars);

        dfs(0,0 ,"");

        System.out.println(sb);
    }

    private static void dfs(int idx, int cnt , String password) {
        //종료
        if (cnt == L) {
            if(check(password)){ // 유효하면 저장
                sb.append(password).append("\n");
            }
            return;
        }

        //확장
        for (int i = idx; i < C; i++) { // 범위가 현재인덱스 ~ C 까지 !
            if(!isSelected[i]){
                isSelected[i] = true;
                dfs(i + 1, cnt + 1, password + chars[i]); // 재귀 처리
                isSelected[i] = false;
            }
        }
    }

    private static boolean check(String password) {
        int mo = 0;
        int ja = 0;
        for (char c : password.toCharArray()) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                mo++; // 최소 한개의 모음
            } else {
                ja++; // 최소 두개의 자음
            }
        }

        if(mo >= 1 && ja >= 2){
            return true;
        }else {
            return false;
        }
    }
}

password.toCharArray() string을 char 배열로!

isSelected 를 안쓰고??

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

public class Main {
    static int L, C;
    static char[] characters;
    static StringBuilder sb = new StringBuilder();

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        characters = new char[C];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            characters[i] = st.nextToken().charAt(0);
        }

        Arrays.sort(characters); // 정렬

        solve(0, 0, "");

        System.out.println(sb.toString());
    }

    static void solve(int start, int count, String password) {
        if (count == L) {
            // 자음과 모음의 조건을 만족하는지 확인
            if (checkPassword(password)) {
                sb.append(password).append("\n");
            }
            return;
        }

        for (int i = start; i < C; i++) {
            solve(i + 1, count + 1, password + characters[i]);
        }
    }

    static boolean checkPassword(String password) {
        int vowelCount = 0; // 모음 개수
        int consonantCount = 0; // 자음 개수

        for (char c : password.toCharArray()) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vowelCount++;
            } else {
                consonantCount++;
            }
        }

        return vowelCount >= 1 && consonantCount >= 2;
    }
}

📌 필요없는 이유

• 현재 인덱스(start)부터 끝까지의 문자를 탐색
• 각 단계에서 for 루프를 통해 다음 문자를 선택하고 재귀 호출하면서, 이미 선택한 문자 이전의 문자는 다시 선택하지 않음
• 현재 선택된 문자 이후의 문자만을 고려하기 때문에, isSelected 배열을 사용하지 않고도 중복 선택을 피할 수 있다 !!
  👉 즉 start부터 C까지의 범위에서만 반복하면서 재귀 호출을 진행하므로, 이미 선택된 문자 이전의 문자는 고려 대상 아님 !!
  

🤔 다른 최적화 방법

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

public class Main2 {
    static int L, C;
    static char[] arr;
    static StringBuilder sb = new StringBuilder();
    static boolean[] selected;

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

        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[C];
        selected = new boolean[C];

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

        Arrays.sort(arr);

        dfs(0, 0, 0, 0); // 모음, 자음 개수 초기화

        System.out.println(sb);
    }

    static void dfs(int idx, int size, int mo, int ja) {
        // 종료 조건: L개의 문자를 선택했을 때
        if (size == L) {
            // 모음 1개 이상, 자음 2개 이상인 경우
            if (mo >= 1 && ja >= 2) {
                for (int i = 0; i < C; i++) {
                    if (selected[i]) {
                        sb.append(arr[i]);
                    }
                }
                sb.append('\n');
            }
            return;
        }

        // 확장: 현재 인덱스부터 탐색
        for (int i = idx; i < C; i++) {
            if (!selected[i]) {
                selected[i] = true;

                // 모음, 자음 개수 갱신
                if (isVowel(arr[i])) {
                    dfs(i + 1, size + 1, mo + 1, ja);
                } else {
                    dfs(i + 1, size + 1, mo, ja + 1);
                }

                selected[i] = false;
            }
        }
    }

    static boolean isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}