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

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

 

비트마스크 활용 문제입니다.

문자열을 마스크로 바꿔서 저장해둔 뒤, 쿼리가 발생할 때마다 모든 문자열과 현재 알고있는 알파벳 마스크를 적당히 연산을 해서 읽을 수 있는지 없는지 확인합니다.

읽을 수 있는지 없는지 체크하는 방법은 (현재 알고 있는 알파벳 마스크 & 단어 마스크) == 단어 마스크 가 되면 됩니다. 적당히 그림을 그려 보면 바로 이해가 되실겁니다.

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	string s;
	vector<int> words(n);
	for (auto& w : words) {
		cin >> s;
		
		for (auto& c : s) {
			w |= 1 << (c - 'a');
		}
	}

	int brain = 0x3ffffff;

	int q;
	char ch;
	while (m--) {
		cin >> q >> ch;
		
		if (q == 1) {
			// forget
			brain &= ~(1 << (ch - 'a'));
		}
		else {
			// remember
			brain |= 1 << (ch - 'a');
		}


		int readable = 0;
		for (auto& w : words) {
			if ((brain & w) == w)
				++readable;
		}
		cout << readable << '\n';
	}


	return 0;
}

사실 문제를 대충 읽고 모음 관련 처리를 안했는데 통과가 됩니다.

'모음은 완벽하게 외웠기 때문에 절대 잊지 않는다'라는 것이 입력으로 자음이 절대 안들어온다는 의미같습니다. 게시판에 보니 그런 느낌의 답변이 있네요.