[C++] 백준 18119번: 단어 암기

문제 링크

18119번: 단어 암기

문제 요약

N개의 영단어가 입력으로 주어진다. 초기에는 모든 알파벳을 알고 있는 상태이다. 이때 다음의 쿼리를 수행할때마다 알고 있는 알파벳으로 표현할 수 있는 단어의 수를 출력해야 한다.
1 x : 알파벳 x를 잊는다.
2 x : 알파벳 x를 기억해 낸다.

접근 방법

비트마스킹을 쓰면 간단하게 풀 수 있습니다. 단어를 입력 받을 때, 비트 시프트 연산자를 이용해서 단어를 표현하는데 필요한 알파벳들을 숫자로 바꿔서 저장합니다.

그리고 이제 알고 있는 알파벳들을 비트로 표현해줍니다. 총 26개의 알파벳을 알고 있기 때문에 (1 << 27) - 1을 변수에 저장해주면, 26개의 비트만 켜지게 됩니다.

이제 1번 쿼리를 수행하면 해당 위치의 비트를 0으로 만들고, 2번 쿼리를 수행하면 해당 위치의 비트를 1로 만들어 주면 됩니다.

그리고 앞서 저장한 숫자들과 현재 알고 있는 알파벳을 나타내는 숫자를 & 연산한 결과가 저장된 숫자와 같다면 표현이 가능한 것이기 때문에 카운트해주고, 매 쿼리마다 이 카운트 횟수를 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;

		for (auto& j : str)
			v[i] |= 1 << j - 'a';
	}

	int bits = (1 << 27) - 1;
	while (m--) {
		int q;
		char c;
		cin >> q >> c;

		if (q == 1)
			bits -= 1 << c - 'a';
		else
			bits += 1 << c - 'a';

		int cnt = 0;
		for (auto& i : v)
			if ((i & bits) == i)
				cnt++;
		cout << cnt << '\n';
	}

	return 0;
}