BOJ 1759 암호 만들기 [Java]

BOJ 1759 암호 만들기

1. 문제 링크

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

2. 문제 해설

백트래킹 문제이다. 다만 조건이 조금 추가되었다. 어떤 조건이 있는지 살펴보자.
1. 암호는 L개의 알파벳 소문자로 구성된다.
2. 최소 한 개의 모음과 두 개의 자음으로 구성된다.
3. 알파벳이 사전 순으로 배열된다.

일단 solve 메서드가 받아야할 인자는 현재 암호의 길이(length), 살펴보고 있는 인덱스(idx), 모음의 수(vowel), 자음의 수(consonant)이다.
solve 메서드가 1, 2번 조건을 만족할 때 탈출하여 문제의 조건을 만족시켜준다.
3번째 조건인 암호의 경우의 수가 사전 순으로 배열되게 하기 위해서 입력 받은 arr 배열을 미리 사전 순으로 정렬해준다.
52 ~ 66번째 줄이 핵심 로직이다.
idx부터 루프를 돌면서 지난 인덱스의 알파벳을 방문하지 않는다.
현재 방문한 인덱스의 알파벳이 모음이면 모음 갯수를 1개 늘려주고, 자음이면 자음 갯수를 1개 늘려서 solve 메서드를 재귀적으로 호출해준다.

3. 코드 보기

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int l, c;
    static char[] arr;
    static boolean[] vis;
    static StringBuilder sb = new StringBuilder();

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

        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        arr = new char[c];
        vis = new boolean[c];

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

        Arrays.sort(arr);

        solve(0, 0, 0, 0);

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    static void solve(int length, int idx, int vowel, int consonant) {
        if (length == l) {
            if (vowel < 1 || consonant < 2) {
                return;
            }

            for (int i = 0; i < c; i++) {
                if (vis[i]) {
                    sb.append(arr[i]);
                }
            }

            sb.append("\n");
            return;
        }

        for (int i = idx; i < c; i++) {
            if (vis[i]) {
                continue;
            }

            vis[i] = true;

            if (isVowel(arr[i])) {
                solve(length + 1, i + 1, vowel + 1, consonant);
            } else {
                solve(length + 1, i + 1, vowel, consonant + 1);
            }

            vis[i] = false;
        }
    }

    static boolean isVowel(char a) {
        if (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u') {

            return true;
        } else {
            return false;
        }
    }
}