[백준 / 골드4] 1062 가르침 (Java)

문제 보기

사용한 것

• 가르친 단어들의 조합을 구하기 위한 DFS
• 가르친 단어들을 순서에 상관없이 저장하기 위한 HashSet
  • add()와 contains()의 속도가 O(1)이라서 사용

풀이 방법

• K를 입력 받은 값 - 5로 저장한다. ('a', 'n', 't', 'i', 'c' 는 기본적으로 필요한 글자이기 때문에 제외시킬 것이기 때문이다.)
• 제외한 글자 외 단어들을 words에 담는다.
• K가 0보다 작으면 기본적인 "antatica"도 만들 수 없으므로 0을 출력한다.
• DFS를 시작한다.
• 가르친 글자들의 조합 learned에 글자들을 넣으며 depth를 1씩 증가시킨다.
• depth가 최대로 가르칠 수 있는 K와 같아지면 몇 개의 단어를 사용할 수 있는지 확인하여 max보다 크면 갱신한다.
• max를 출력한다.

코드

public class Main {

    static Set<Character> learned = new HashSet<>();
    static char[] alphabets = {'b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 'q',
        'r', 's', 'u', 'v', 'w', 'x', 'y', 'z'};
    static int N;
    static int K;
    static String[] words;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] split = line.split(" ");
        N = Integer.parseInt(split[0]);
        words = new String[N];
        K = Integer.parseInt(split[1]) - 5;
        for (int i = 0; i < N; i++) {
            line = br.readLine();
            StringBuilder word = new StringBuilder();
            for (int j = 0; j < line.length(); j++) {
                char c = line.charAt(j);
                if (c == 'a' || c == 'n' || c == 't' || c == 'i' || c == 'c') {
                    continue;
                }

                word.append(c);
            }

            words[i] = word.toString();
        }

        if (K < 0) {
            System.out.println(0);

            return;
        }

        dfs(0, -1);

        System.out.println(max);
    }

    static void dfs(int depth, int lastIdx) {
        if (depth == K) {
            int ct = 0;
            for (String word : words) {
                boolean contains = true;
                for (int i = 0; i < word.length(); i++) {
                    if (!learned.contains(word.charAt(i))) {
                        contains = false;

                        break;
                    }
                }
                if (contains) {
                    ct++;
                }
            }

            if (ct > max) {
                max = ct;
            }
        }

        for (int i = lastIdx + 1; i < alphabets.length; i++) {
            char c = alphabets[i];
            learned.add(c);
            dfs(depth + 1, i);
            learned.remove(c);
        }
    }
}