[백준/C++] 18119. 단어 암기

문제

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

18119번: 단어 암기

준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다.
다음과 같은 쿼리들이 주어진다.

• 1 x : 알파벳 x를 잊는다.
• 2 x : 알파벳 x를 기억해 낸다.

처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.
각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.

풀이

길이 26짜리 비트맵을 이용해서 풀이했다. (알파벳 개수가 26이기 때문)
처음에는 모든 알파벳을 기억하고 있으므로 전부 1로 설정하고
특정 알파벳을 잊을 때는, 해당 자리의 비트를 0으로 바꿔주고
다시 기억할 때는, 해당 자리의 비트를 1로 바꾸어주었다.
(a=0, b=1번 째 자리 비트)

기억하는 연산 (1로 바꾸는 연산)은 or로 편하게 했는데,
잊어버리는 연산 (0으로 바꾸는 연산)은 한줄에 어떻게 처리해야할지 모르겠어서 if를 통해 해당 자리 비트가 1이면, 해당 수를 빼는 방법으로 계산했다.

N개의 단어들은 입력받을 때 비트맵으로 변환해서 저장하고,
그리고 매번 쿼리마다 N개의 단어를 모두 확인해서 해당 쿼리에 기억하고 있는 단어의 개수를 세주었다.

[의문점]
다 풀고 문제를 다시보니, 모음은 절대로 잊지 않는다는 조건이 있었다. 이 부분을 따로 처리해주지 않았는데 정답이 나온걸 보니, 아예 모음을 잊는 쿼리가 테스트케이스에 안들어오는 것 같다.

코드

#include <iostream>
#include <string>

using namespace std;

int bitmap = (1 << 27)-1;
int N, M;
int bitmaps[10001];
int main() {
	scanf("%d %d", &N, &M);
	string word;
	for (int n = 0;n < N;n++) {
		cin >> word;
		int bm = 0;
		for (int i = 0;i < word.size();i++) {
			int temp = word[i]-'a';
			bm = bm | (1 << temp);
		}
		bitmaps[n] = bm;
	}
	char x; int o;
	for (int m = 0;m < M;m++) {
		scanf("%d %c", &o, &x);
		int idx = x - 'a';
		int temp = (1 << idx);
		if (o == 1) { // x 잊기 
			if ((bitmap & temp) == temp) {
				bitmap -= temp;
			}
		}
		else if (o == 2) { // x 기억하기
			bitmap = bitmap | temp;
		}
		// 단어중에 몇 개 기억하는지 
		int cnt = 0;
		for (int n = 0;n < N;n++) {
			int res = bitmap & bitmaps[n]; 
			if (res == bitmaps[n])
				cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

결과