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

비트마스킹 문제입니다.

기억하고 있는 알파벳과 단어에 대해서 각각 비트마스크로 처리합니다.
그리고 해당 비트연산을 통해서 해당 알파벳을 포함하는지 확인하는 과정을 합니다.

비트마스킹으로 문제를 풀면 한 단어를 계산할 때 한번의 작업이 들지만
일반적으로 비교연산으로 처리하면 알파벳 한 단어를 계산할 때 단어의 길이만큼 작업이 듭니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define MAX_BIT 67108863
using namespace std;

int n, m;
int alphabet = MAX_BIT;
vector<int> word(10000);

void solution()
{
  int num;
  int count = 0;
  char alp;
  string s;

  cin >> n;
  cin >> m;

  for (int i = 0; i < n; ++i)
  {
    cin >> s;
    sort(s.begin(), s.end());

    for (int j = 0; j < s.length(); ++j)
    {
      word[i] = word[i] | 1 << (s[j] - 97);
    }
  }

  for (int i = 0; i < m; ++i)
  {
    count = 0;

    cin >> num;
    cin >> alp;

    if (num == 1)
    {
      alphabet = alphabet & (MAX_BIT - (1 << (alp - 97)));
    }
    else
    {
      alphabet = alphabet | 1 << (alp - 97);
    }
    for (int j = 0; j < n; ++j)
    {
      if (((MAX_BIT - word[j]) | alphabet) == MAX_BIT)
      {
        ++count;
      }
    }
    cout << count << endl;
  }
}

int main(int argc, char *argv[])
{
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  solution();

  return 0;
}