BOJ (Java) 1062번: 가르침

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

---

풀이

규칙이 있는 줄 알았으나 파악하지 못 해 알고리즘을 봤다.

비트마스킹이 있어 각 단어들에 포함된 알파벳을 int형 정수에 비트마스킹으로 표시했다.

배울 문자들을 확인할 때도 비트마스킹을 활용, 각 비트의 자리에 알파벳을 표시했다.

 

이후 브루트포스로 탐색하며 K개의 문자를 배웠을 때 현재 읽을 수 있는 단어가 몇 개인지 확인하여 최댓값을 반환한다.

이 때 현재 단어를 읽을 수 있다면 배운 문자들에 현재 단어가 포함되어야 되므로 & 연산을 활용해 확인했다.

---

Java 코드

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

public class Main {

    private static int N, K;
    private static int answer = 0;
    private static int[] words;

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        K = Integer.parseInt(inputs[1]);

        // K < 5 일 때 'anta', 'tica'에 들어가는 글자조차 배우지 못함, 0 반환
        if (K < 5) {
            System.out.println(0);
            return;
        }
        K -= 5;

        // N개의 문자열 입력 받기
        words = new int[N];
        for (int i = 0; i < N; i++) {
            String input = bf.readLine();

            // 알파벳이 26자리이므로 27자리의 수를 생성
            int tmp = 1 << 27;

            // 'anta', 'tica'를 제외한 중간의 문자들 중 배워야 할 단어를 비트마스킹으로 표시
            for (int j = 4; j < input.length() - 4; j++) {
                tmp |= 1 << (input.charAt(j) - 'a');
            }
            words[i] = tmp;
        }

        // 배워야 할 문자들을 표시할 숫자에 'anta', 'tica' 기본값으로 넣어줌
        int learned = 1 << 27;
        learned |= (1 << 'a' - 'a');
        learned |= (1 << 'n' - 'a');
        learned |= (1 << 't' - 'a');
        learned |= (1 << 'i' - 'a');
        learned |= (1 << 'c' - 'a');

        findMax(0, learned, 0);
        System.out.println(answer);
    }

    private static void findMax(int cnt, int learned, int idx) {
        // K 개의 문자를 모두 배웠다면 읽을 수 있는 단어의 개수 세기
        if (cnt == K) {
            answer = Math.max(answer, getReadableCnt(learned));
            return;
        }

        // 알파벳을 하나씩 순회하며 배우지 않은 문자들을 배움, 이 때 중복 방지를 위해 전에 배운 문자의 다음부터 순회
        for (int i = idx; i < 26; i++) {
            if ((learned & (1 << i)) == 0) {
                findMax(cnt + 1, learned | (1 << i), i + 1);
            }
        }
    }

    // 읽을 수 있는 단어의 개수 찾기
    private static int getReadableCnt(int learned) {
        int readableCnt = 0;
        for (int i = 0; i < N; i++) {
            // 읽을 수 있다면 배운 문자들(learned)에 현재 단어(words[i])가 포함되어 있음
            // & 연산 시 words[i]가 나옴
            if ((learned & words[i]) == words[i]) {
                readableCnt++;
            }
        }
        return readableCnt;
    }
}