백준 1759 - 암호 만들기

문제

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

리뷰

백트래킹을 이용하여 풀이할 수 있는 간단한 문제였다.

암호를 구성할 문자들을 저장할 values 배열과 암호를 구성하는데
사용할 arr 배열을 정의하였다. 이후 dfs를 이용한 백트래킹을 통해
depth가 L과 같을 때(암호가 다 구성되었을때) check 를 통해
암호의 모음, 자음 포함 여부를 검사한 후 조건에 맞으면 답안에 추가하고
탐색을 중단하는 식으로 로직을 구성하였다. 백트래킹 로직내에서 이전 문자보다
다음으로 탐색할 문자가 큰 경우(알파벳이 암호에서 증가하는 순서일 경우)만
탐색을 지속하도록 로직을 구성하여 해당 조건을 충족시켰다.

해당 로직의 시간복잡도는 check 함수가 $O(L)$, dfs 로직이 최악의 경우
$O(C^2)$으로 수렴하므로 문제의 시간 제한 조건인 2초를 무난하게 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int L, C;
    static char[] values;
    static char[] arr;
    static List<String> answer = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());

        L = parseInt(st.nextToken());
        C = parseInt(st.nextToken());

        values = new char[C];
        arr = new char[L];

        st = new StringTokenizer(in.nextLine());
        for (int i = 0; i < values.length; i++)
            values[i] = st.nextToken().charAt(0);

        dfs(0);
        Collections.sort(answer);
        answer.forEach(ans -> System.out.println(ans));
        in.close();
    }

    static void dfs(int depth) { // O(C^2)
        if (depth == L) {
            String ans = new String(arr);
            if (check(ans))
                answer.add(ans);
            return;
        }

        for (char next : values) {
            if (depth == 0) {
                arr[depth] = next;
                dfs(depth + 1);
            } else {
                if (arr[depth - 1] < next) {
                    arr[depth] = next;
                    dfs(depth + 1);
                }
            }
        }
    }


    static boolean check(String password) {
        boolean isIncludeVowel = false;
        boolean isIncludeConsonant = false;

        int consonantCount = 0;
        Character pre = 'a';

        for (int i = 0; i < password.length(); i++) { // O(L)
            Character c = password.charAt(i);

            switch (c) {
                case 'a':
                case 'e':
                case 'i':
                case 'o':
                case 'u':
                    isIncludeVowel = true;
                    break;

                default:
                    consonantCount++;
            }
        }

        if (consonantCount >= 2)
            isIncludeConsonant = true;

        return isIncludeVowel && isIncludeConsonant;
    }
}

결과