BOJ - 단어 암기(18119)

문제(링크)

n개의 알파벳 중 모르는 단어가 하나라도 포함되어 있는지 판단하는 문제였습니다.

처음엔 Trie 알고리즘으로 접근했으나 메모리 초과가 떴습니다.

알파벳의 개수가 26개밖에 안되므로 알파벳을 아는지(1) 모르는지(0) 를 비트마스크로 나타내서 풀면 간단해지는 문제입니다.

처음엔 모든 알파벳을 알고 있다고 했으므로 know = 11111111111... 로 초기화 해줍니다.

문자를 잊는 연산은 ^ , 문자를 기억하는 연산은 | 로 쉽게 구할 수 있습니다.

마지막으로 각 쿼리마다 모든 문자열에 대해 

(아는 문자들 & 문자열) == 문자열 

인 경우에 대해 카운트하여 출력하면 됩니다.

#include<iostream>
#include<string>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int, int>;

int N, M;
int bit[10000];

int main(void) {
 FIO;

 cin >> N >> M;

 for (int i = 0; i < N; i++)
 {
  string str;
  cin >> str;

  for (int j = 0; j < str.size(); j++)
  {
   bit[i] = bit[i] | (1 << (str.at(j) - 'a'));
  }
 }
 int know = 67108863;

 for (int i = 0; i < M; i++)
 {
  int q;
  char x;
  int cnt = 0;
  
  cin >> q >> x;
  
  if (q == 1) {
   know = know ^ (1 << (x - 'a'));
   for (int j = 0; j < N; j++)
   {
    if ((know & bit[j]) == bit[j])
     cnt++;
   }
  }
  else {
   know = know | (1 << (x - 'a'));
   for (int j = 0; j < N; j++)
   {
    if ((know & bit[j]) == bit[j])
     cnt++;
   }
  }
  cout << cnt << "\n";
 }
}