문제

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

---

입력

첫 번째 줄에는 정수 N과 M이 주어진다.
다음 N개의 줄에는 문자열이 하나씩 주어진다.
다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다.

---

출력

각 쿼리마다 정수 하나를 출력한다.

---

풀이

제한조건

• 4초 1024MB
• (1 ≤ N ≤ 10^4)
• (1 ≤ M ≤ 5×10^4)
• 문자열의 길이는 103을 넘지 않는다.
• o는 1, 2중 하나이고, x는 알파벳 소문자이다.
• o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

접근방법

비트마스킹

메모리가 넉넉하기에, 비트마스킹 없이 풀어도 문제가 풀릴 것으로 보인다.
하지만, 비트마스킹으로 풀어보자.

단어가 알파벳 소문자로 주어지므로, int형 변수(32비트)에 모두 담을 수 있다.

      zy xwvutsrq ponmlkji hgfedcba
00000000 00000000 00000000 00000000

즉, 단어가 apple 라면, 아래와 같이 저장한다.

      zy xwvutsrq ponmlkji hgfedcba
00000000 00000000 10001000 00010001

그리고 각 쿼리에 대한 입력을 받으며 해당 알파벳 위치에 적절한 연산을 통해
비트를 켜거나, 끈다.
그 후, 입력된 단어들과 비트연산을 통해 해당 단어의 알파벳을 모두 알고 있는지 확인한다.

특정 단어를 알고있는지 확인하는 방법 ( &연산의 특성 활용)

A : 기존에 알고있는 알파벳
B : 입력된 단어
A & B == B
 - true : 모두 알고 있음.
 - false : 모르는 알파벳이 최소 1개 이상 존재함.

정리하자면 다음과 같다.

1. 기존에 알고 있는 단어를 비트로 저장.
2. 입력 단어들을 비트화 하여 저장.
3. o의 값에 따라, 특정 비트를 1 또는 0으로 변경.
4. 기존에 알고 있던 단어와 입력 단어들을 &연산 수행.
5. 카운팅.

---

코드

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

public class Main {
	static int N, M;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		M = stoi(inputs[1]);

		// 입력 단어들을 bit화
		int[] arr = new int[N];
		for (int i = 0; i < N; ++i) {
			String s = in.readLine();
			for (int j = 0; j < s.length(); ++j)
				arr[i] = arr[i] | (1 << (s.charAt(j) - 'a'));
		}

		// 미리 알고 있는 단어 기록
		int base = 0;
		base = 1 << 'z' - 'a' + 2;
		base -= 1;

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; ++i) {
			inputs = in.readLine().split(" ");
			if (inputs[0].equals("1")) {
				base = base & ~(1 << (inputs[1].charAt(0) - 'a'));
			} else {
				base = base | (1 << (inputs[1].charAt(0) - 'a'));
			}

			final int finalBase = base;
			int count = (int)Arrays.stream(arr)
				.filter(a -> (a & finalBase) == a) // 조건에 맞는것만
				.count(); // 카운트
			sb.append(count).append("\n");
		}
		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}