[백준 18119] 단어 암기 (Java)

문제 링크: https://www.acmicpc.net/problem/18119

18119번: 단어 암기

1. 주의할 점

- 비트마스크를 이용하여 문제를 해결한다

 

2. 구현

- 기억하고 있는 알파벳의 상태를 curKnow 변수에 저장한다. 초기에는 26가지 모두 알고 있으므로 curKnow = (1<<27)-1를 수행한다

- Arr[] 배열을 초기화시킨 후, 각 문자열에 존재하는 알파벳을 연산을 통해 Arr[]배열에 저장한다

- 쿼리문에서 처음으로 입력받는 수가 1일 경우, 해당 알파벳을 잊어야하므로 &와 ~연산을 수행한다

- 2일 경우, | 연산을 수행한다

- curKnow와 Arr[]수를 &한 결과가 Arr[]와 같다면, 해당 문자열을 완벽히 기억하고 있으므로 Cnt++를 수행한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    int num = Integer.parseInt(st.nextToken());
	    int query = Integer.parseInt(st.nextToken());    
	    int curKnow = (1<<27)-1;
	    int arr[] = new int[num];

	    for(int i=0;i<num;i++){
	        str = br.readLine().trim();
	        long l = 0;
	        for(int j=0;j<str.length();j++){
	            char c = str.charAt(j);
	            int a = c-'a';
	            arr[i] |= (1<<a);
	        }
	    }
	    
	    for(int i=0;i<query;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int flag = Integer.parseInt(st.nextToken());        //1: 잊음, 2:기억
	        int a = st.nextToken().charAt(0)-'a';	        
	        if(flag==1) curKnow &= ~(1<<a);
	        else curKnow |= (1<<a);
	        
	        int cnt=0;
	        for(int j=0;j<num;j++){
	            int l = arr[j];
	            if((l&curKnow) == l) cnt++;
	        }
	        System.out.println(cnt);
	    }
	}
}