[18119 단어 암기]

• 문제 - www.acmicpc.net/problem/18119

18119번: 단어 암기

 

• 분석 및 해결

기억하고 있는 알파벳의 상태가 매번 바뀌며, 알고 있는 알파벳 상태를 기준으로 N개의 쿼리에 대해 탐색을 실행해야 한다. 따라서, 쿼리의 개수 최대 10,000개, 각 쿼리의 최대 길이 1,000, 알고 있는 알파벳 상태의 변화 최대 10,000번이므로 최대 10의 11승으로 단순하게 반복문을 돌리게 되면 시간 초과가 발생하게 된다.

 

이런 경우, 비트마스킹을 사용하게 되면 탐색 시간을 줄일 수 있기에 비트마스킹 기법을 활용해 문제를 해결했다.

 

• 소스 코드

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

public class BJ_18119 {

	private static int N, M, visited = Integer.MAX_VALUE;
	private static int binary[]; // 각 쿼리마다 사용된 알파벳을 저장하는 배열
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		binary = new int[N];
		
		for(int iter = 0; iter < N; iter++) {
			String query = br.readLine();
			
			for(int index = 0; index < query.length(); index++) {	
				// 쿼리에서 사용되는 알파벳을 체크
				binary[iter] |= (1 << (query.charAt(index) - 97));
			}
		}
		
		for(int iter = 0; iter < M; iter++) {
			String[] param = br.readLine().split(" ");
			
			int cmd = Integer.parseInt(param[0]);
			int cnt = param[1].charAt(0) - 97;
			int shift = 1 << cnt;
			
			// 알파벳을 기억하게 되는 경우
			if(cmd == 1) {
				visited ^= shift;
			}
			// 알파벳을 까먹게 되는 경우
			else {
				visited |= shift;
			}
			
			System.out.println(checkQuery());
		}
	}

	private static int checkQuery() {
		int total = 0;
		
		for(int index = 0; index < N; index++) {
			if((binary[index] & visited) == binary[index]) {
				total++;
			}
		}
		
		return total;
	}
}