(백준) 단어암기 - 18119 [java]

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

 

🐢 설명

비트마스킹 문제이다.

 

기억하는 단어, 잊는 단어가 입력으로 주어지는데 이를 기반으로 bit를 on/off 한 후에 기억하는 알파벳과 해당 단어에 대한 비트를 비교해서 전부 on이라면 (즉, 해당 단어의 알파벳들의 비트와 기억하는 단어의 비트가 같다면) 해당 단어는 기억하는 단어로 Count를 올려준다.

 

1. 알파벳 26개에 대한 bit 26개를 전부 1로 켜준다 -> (1 << 27) - 1
   • 100000000000000000000000000 -> 11111111111111111111111111 (26개)
2. 주어지는 단어에 대해서 각 단어 별로 해당하는 알파벳을 켜준다.
   • db -> 1010
   • za -> 10000000000000000000000001
3. 각 단어를 잊거나 기억하는 조건에 따라 알파벳을 꺼주거나 켜준다
   • 기억하는 경우 : 1로 켜준다
     • if C == d : alphabet & (1 << C - 'a') -> 알파벳 26비트 & 1000 연산, 알파벳의 d가 켜진다. 나머지에 대해선 영향이 없다.
   • 잊는 경우 : 0으로 꺼준다
     • if C == d : alphabet | ~(1 << C - 'a') -> 알파벳 26비트 | 0111 연산, 알파벳의 d가 꺼진다. 나머지에 대해선 영향이 없다.
4. 알파벳과 모든 단어 목록에 대해서 & 연산을 해준다.
   • 만약 단어와 알파벳의 &연산이 단어와 같다면 : 해당 단어에 해당하는 알파벳을 모두 알고있다
   • 다르다면 (작다면) : 해당 단어에 해당하는 알파벳 중 잊고 있는게 있다

🐢코드

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

public class Main {
    static int N, Q;

    // 모든 알파벳을 알고 있다.
    // 100000000000000000000000000 -> 11111111111111111111111111
    static int alphaBit = (1 << 27) - 1;
    static int[] wordBits;

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

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        // 각 단어에 대한 알파벳 체크
        wordBits = new int[N];

        for (int i = 0; i < N; i++) {
            for (char c : br.readLine().toCharArray()) {
                // a -> 1
                // b -> 10
                // c -> 100
                // db -> 1010
                wordBits[i] |= (1 << c - 'a');
            }
        }

        for (int q = 0; q < Q; q++) {
            st = new StringTokenizer(br.readLine());

            int option = Integer.parseInt(st.nextToken());
            char forgetC = st.nextToken().charAt(0);

            // 해당 단어를 잊게한다. -> 해당 단어만 0으로 바꾸고 & 연산
            if (option == 1) {
                alphaBit &= ~(1 << forgetC - 'a');
            }
            // 해당 단어를 기억하게 한다. -> 해당 단어를 1로 만들고 | 연산
            else {
                alphaBit |= (1 << forgetC - 'a');
            }

            int rememberWordCount = 0;
            for (int wordbit : wordBits) {
                // wordbit : dif -> 100101000
                // alphabit : 11111111111111111111111111 (기억하는 것만 1)
                // 둘다 1 (기억하면 : 1) -> wordbit가 같다면 기억하는 단어
                if ((wordbit & alphaBit) == wordbit)
                    rememberWordCount++;
            }
            answer.append(rememberWordCount).append("\n");
        }
        System.out.print(answer);
    }
}

 

🐢 마무리

비트마스킹 문제인거를 알고 푼다면 생각할 수 있을텐데 그렇지 않아 처음에 해매게 되었다. 머릿속에 다양한 알고리즘을 떠올리면서 무엇을 사용해야할지 떠올리는게 중요한것 같다.