문제

김지민쌤이 학생들에게 되도록 많은 단어를 읽을 수 있도록 k개의 글자를 알려주실 예정이다. 몇 개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어가 최대가 될까

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

풀이

• visited[26] : 각 알파벳의 사용 여부 체크
• words[n] : 단어들을 저장한다. ('anti','tica' 제외)

1. k > 5거나 k == 26일때
   어떤 단어도 읽을 수 없고, 모든 단어를 읽을 수 있는 경우이므로 알맞은 값을 출력 후 종료한다.

2. visited에 무조건 배울 수 밖에 없는 단어를 true로 바꾼다.

3. check() 함수로 최대값을 구한다.
   해당 알파벳부터 조합을 구해서 check를 재귀호출한다.

4. count의 값이 k-5와 같으면 (antic은 이미 배움)
   단어에 배우지 않은 알파벳이 있는 경우를 제외한 케이스를 모두 더해 최대값을 구한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1062 {
    static int n;
    static int k;
    static boolean[] visited;
    static String[] word;
    static int answer = 0;

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

        String[] input = br.readLine().split(" ");

        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        visited = new boolean[26];
        word = new String[n];

        if (k < 5) {
            System.out.println(0);
            return;
        } else if (k == 26) {
            System.out.println(n);
            return;
        }

        /* 무조건 배워야하는 단어 */
        visited['a' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['c' - 'a'] = true;

        for (int i = 0; i < n; i++) {
            String str = br.readLine().replaceAll("anta|tica", "");

            word[i] = str;
        }

        check(0, 0);
        System.out.println(answer);
    }

    static void check(int alpha, int count) {
        if (count == k - 5) {
            int temp = 0;
            for (int i = 0; i < n; i++) {
                boolean flag = true;

                for (int j = 0; j < word[i].length(); j++) {
                    /* 배우지않은 알파벳이 있는 경우 */
                    if (!visited[word[i].charAt(j) - 'a']) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    temp++;
                }
            }
            answer = Math.max(temp, answer);
            return;
        }

        for (int i = alpha; i < 26; i++) {
            if (!visited[i]) {
                visited[i] = true;
                check(i, count + 1);
                visited[i] = false;
            }
        }
    }

}

처음에는 비트마스크가 더 적합할 것이라고 생각해서 풀다가 하루를 비트마스크로 날려버리고.. 그냥 boolean 배열로 체크해서 풀었다.. 💧
아무리 봐도 비트마스크로 푸는 게 더 나을 듯
꼭 비트마스크로 다시 해결한다