[백준] 1062번 : 가르침 - JAVA [자바]

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

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝나기 때문에 이 단어에 들어가는 글자 a, n, t, i, c 총 5 개의 글자는 알아야 단어를 알 수 있다.

그러므로 K 개의 글자를 가르칠 때, K가 5보다 작으면 모든 단어를 알 수 없으므로 0을 출력한다. 또한, K가 26개의 글자 즉, 모든 알파벳의 갯수를 가르칠 수 있으면 N 개의 단어를 모두 배울 수 있으므로 N 개를 출력한다.

그 외에 대해서는 a, n, t, i, c 총 5 개의 글자는 필수로 알아야 하므로 boolean 배열을 만들어서 저 알파벳들은 true 로 초기화 한다.

그 후 N 개의 단어들을 입력 받는데 이때, 모든 단어의 공통인 앞 뒤 "anta"로 시작되고, "tica"로 끝나는 부분은 필요 없으므로 그 사이의 단어만 입력 받는다.

그 후 K - 5 개의 글자(K개의 글자를 배울때 a, n, t, i, c 총 5 개의 글자는 필 수로 알아야 하므로)를 선택하여 배울 때 가장 단어를 많이 읽을 수 있을 때의 최대 값을 구한다.

이때, 알파벳을 선택하는 순서가 달라도 같은 것을 의미하므로 중복이 생길 수 있다. 이를 해결하기 위해 index 값도 같이 넘겨줘서 중복이 발생하지 않도록 하면 시간 초과 문제를 해결할 수 있다.

public class bj1062 {

    public static int N, K, answer = 0;
    public static boolean[] alphabet = new boolean[26];
    public static String[] words;

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

        String line = br.readLine();
        String[] split = line.split(" ");
        N = Integer.parseInt(split[0]);
        K = Integer.parseInt(split[1]);
        words = new String[N];

        if (K < 5) {
            System.out.println(0);
            System.exit(0);
        } else if (K == 26) {
            System.out.println(N);
            System.exit(0);
        }

        // anta + tica
        // a, c, n, t, i -> 5 개는 필수로 알아야 한다.
        alphabet[('a' - 'a')] = true;
        alphabet[('c' - 'a')] = true;
        alphabet[('n' - 'a')] = true;
        alphabet[('t' - 'a')] = true;
        alphabet[('i' - 'a')] = true;

        for (int i = 0; i < N; i++) {
            String str = br.readLine().replaceAll("anta|tica", "");
            words[i] = str;
        }

        dfs(0, 0);

        bw.write(answer + "\n");

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

    public static void dfs(int index, int depth) {
        if (depth == K - 5) {
            int count = 0;
            for (String word : words) {
                char[] charArray = word.toCharArray();
                boolean canRead = true;
                for (char c : charArray) {
                    if (!alphabet[c - 'a']) {
                        canRead = false;
                        break;
                    }
                }
                if (canRead) count++;
            }
            answer = Math.max(count, answer);
            return;
        }

        for (int i = index; i < 26; i++) {
            if (!alphabet[i]) {
                alphabet[i] = true;
                dfs(i, depth + 1);
                alphabet[i] = false;
            }
        }
    }

}