[백준] 18119 단어 암기

November 02, 2021 ( last updated : November 02, 2021 )
비트마스킹 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 18119번 단어 암기

[백준] 18119번 단어 암기

백준 18119번

알고리즘 유형

풀이방법

하나씩 비교하기에는 시간 제한이 있어서 비트마스킹을 통해 풀었습니다.

기억하고 있는 알파벳을 memory에 저장하고 비트마스킹을 통해 잊거나 기억할 때 마다 ^연산을 통하여서 계산하였습니다.

이후 &연산자를 통해서 memory와 words를 비교해서 word가 자기 자신이 나온 것만 카운팅합니다.

#include <iostream>
#include <string>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  int n, m;
  int memory = (1<<31) - 1;
  int arr[10001] = {0,};
  cin >> n >> m;

  for (int i=0; i<n; i++) {
    string word;
    cin >> word;
    for(int j=0; j<word.length();j++) {
      int cur = word[j]-'a';
      arr[i] |= 1 << cur;
    }
  }

  for (int i=0; i<m; i++) {
    int state;
    char alphabet;
    cin >> state >> alphabet;

    memory ^= (1 << (alphabet - 'a'));
    
    int cnt = 0;

    for (int j=0; j<n; j++) {
      if((arr[j] & memory) == arr[j]) {
	      cnt++;
      }
    }
    cout << cnt << '\n';
  }
    
  return 0;
}

Originally published November 02, 2021
Latest update November 02, 2021

Related posts :

{# #}