[문제 풀이] 백준 1759번 암호 만들기 _ver 1 JAVA

문제

 

  문제접근 방법   

해당 문제는 L개의 알파벳으로 구성된 암호를 만들고자 하는데 C개의 문자 후보 중에서 L개를 선택하여 암호를 만든다 

조건은 아래와 같다.

 

• 최소 한 개의 모음(a, e, i, o, u) 포함
• 최소 두 개의 자음 포함
• 알파벳은 오름차순으로 구성되어야 함

핵심은 조합과 조건 검사인것 같다. 암호는 오름차순으로 구성되어야 하기 때문에 입력된 문자들을 오름차순 정렬하고 

 

조합으로 L개의 문자를 선택이후 모음이 1개 이상, 자음이 2개 이상인지 조건 체크해 만족하면 저장하는 식이다.

< 최종 코드 >

import java.util.*;

public class Main {
    static int L, C;
    static char[] chars;
    static StringBuilder sb = new StringBuilder();
    static final char[] vowels = {'a', 'e', 'i', 'o', 'u'};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        C = sc.nextInt();
        chars = new char[C];
        for (int i = 0; i < C; i++) {
            chars[i] = sc.next().charAt(0);
        }

        Arrays.sort(chars);
        dfs(0, 0, 0, "");
        System.out.print(sb);
    }

    static void dfs(int depth, int vowelCnt, int consonantCnt, String result) {
        if (result.length() == L) {
            if (vowelCnt >= 1 && consonantCnt >= 2) {
                sb.append(result).append("\n");
            }
            return;
        }

        for (int i = depth; i < C; i++) {
            char ch = chars[i];
            if (isVowel(ch)) {
                dfs(i + 1, vowelCnt + 1, consonantCnt, result + ch);
            } else {
                dfs(i + 1, vowelCnt, consonantCnt + 1, result + ch);
            }
        }
    }

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

먼저 입력 문자들을 오름차순 정렬해주고 dfs를 호출해준다. dfs의 매개변수들은 각각 아래와 같은 의미를 가진다.

 

• depth: 현재 선택된 문자의 위치
• vowelCnt: 모음 개수
• consonantCnt: 자음 개수
• result: 현재까지 만든 문자열

종료조건은 길이가 L이 일때이고 조건 검사를 진행하는데 모음 ≥ 1, 자음 ≥ 2 일 때만 출력하는 식이다.

isVowel은 모음 판단용 도우미 함수정도로 인식하면 된다.

  next_permutation으로도 문제 풀이를 해보았지만 시간초과가 나는것을 확인하였다.