[240503] 알고리즘 리부트 59일차 - 백준 1759 자바

[Part2-Chapter05-Clip04]

- 백준 1759 암호 만들기

사용했을 법한 문자 종류 배열을 오름차순으로 정렬하고 서로 다른 문자를 뽑아야 하기 때문에 방문배열을 활용하고, 문자를 선택할 때 이전에 선택된 문자가 현재 문자보다 알파벳 순 기준으로 앞서도록 처리하면 된다. 또한 자음과 모음 갯수 제한이 있기 때문에 해시 셋으로 모음을 담고 셋을 통해 해당 여부에 따라 갯수를 카운트해주면 된다. 

package BaekJoon.recursion;

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

public class BJ1759 {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static StringTokenizer st;
    public static char[] target;
    public static boolean[] visited;
    public static int l, c;
    public static char[] ans;
    public static HashSet<Character> set;

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

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

        target = new char[c];
        visited = new boolean[c];
        set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < c; i++) target[i] = st.nextToken().charAt(0);

        br.close();

        Arrays.sort(target);

        ans = new char[l];

        password(0, 0, 0);

        bw.flush();
        bw.close();
    }

    private static void password(int curr, int vowel, int consonant) throws IOException {

        if (curr == l) {
            if (vowel > 0 && consonant >= 2) {
                for (char s : ans) bw.write(s);
                bw.write("\n");
            }
            return;
        }

        for (int i = 0; i < c; i++) {


            if (visited[i] || (curr != 0 && ans[curr - 1] > target[i])) continue;

            ans[curr] = target[i];
            visited[i] = true;

            //System.out.println("curr: " + curr + " target[i]: " + target[i]);

            if (set.contains(target[i])) vowel += 1;
            else consonant += 1;

            password(curr + 1, vowel, consonant);
            visited[i] = false;

            if (set.contains(target[i])) vowel -= 1;
            else consonant -= 1;
        }
    }
}