[백준] 18119번 : 단어 암기

18119번: 단어 암기

---

[비트마스킹]

입력으로 N개의 단어가 문자열 형태로 주어지는데, 이를 문자열로 저장하는 것 보다, 어떤 알파벳이 있는지를 알고있으면 단어 전체를 보지 않더라도 이 단어를 알 수 있다.

 

따라서 String[ ]이 아닌, int[ ]에 저장하는 것이 바람직 할 것이다. 비트마스킹에 대해 잘 모른다면 간단하게 정리해둔 포스팅을 참고하자.

[알고리즘] 비트 마스킹(Bit Masking)

각 단어가 갖는 알파벳을 정수 형태로 나타내었다면, 이제 know라는 변수에 담긴 알고있는 알파벳에 대한 정보와 대조해볼 시간이다.

 

0b110101과 0b110111을 어떻게 연산해야 0b1101이 그대로 나올까? 아주 간단하다.

0b110101 & 0b110111 처럼 &(AND)연산을 하면 된다.

 

즉, 단어를 알고있느냐 에 대한 해답은 &으로 해결할 수 있다.

# Code </>

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

public class Main {

    static int[] arr = new int[10001];

    static int know = (1<<26) - 1;
    static boolean isKnow(int idx){

        return (arr[idx] & know) == arr[idx];
    }
    static void disassemble(String word, int idx){

        for(char c:word.toCharArray())
            arr[idx] |= (1 << c-'a');
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i=0; i<n; i++) {
            String word = br.readLine();
            disassemble(word, i);
        }

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

            int v = Integer.parseInt(st.nextToken());
            char c = st.nextToken().charAt(0);

            know = (v==1)? know & ~(1 << c-'a'): know | (1 << c-'a');

            int cnt = 0;
            for(int j=0; j<n; j++)
                if(isKnow(j))
                    cnt++;

            sb.append(cnt).append('\n');
        }
        System.out.print(sb);
    }
}