[BOJ] 18119번 - 단어 암기

18119번 - 단어 암기

문제

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

다음과 같은 쿼리들이 주어진다.

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

처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.

각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.

입력

첫 번째 줄에는 정수 N \(1 ≤ _N_ ≤ $10^{4}$)과 M (1 ≤ M ≤ 5×$10^{4}$)이 주어진다.

다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 $10^{3}$을 넘지 않는다.

다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 소문자이다.

o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

출력

각 쿼리마다 정수 하나를 출력한다.

제한

예제 입력 1

5 10  
apple  
actual  
banana  
brick  
courts  
1 l  
1 b  
1 c  
1 n  
2 l  
2 b  
1 s  
2 c  
2 s  
2 n

예제 출력 1

3  
1  
0  
0  
1  
1  
1  
3  
4  
5

출처

www.acmicpc.net/problem/18119

알고리즘 종류

• 브루트포스 알고리즘
• 비트마스킹

접근 방법

M개의 쿼리마다 저장된 N개의 문자열들과의 비트마스킹 연산을 통해 "기억하고 있는 단어" 이면 cnt를 증가시킴으로서 O(N*M)시간 내에 알고리즘을 구현할 수 있다.
초기의 비트마스크는 모든 단어를 포함하므로 전부 1로 초기화 해주면 된다.

비트마스킹을 위해 소문자 'a'을 포함한다면 0번째 비트에 1을 저장, 'b'를 포함한다면 1번째 비트에 1을 저장 , ... 방식으로 구현하였으며
비트연산을 빠르게 처리 하기 위해 배열로 만들어 원소마다 비교를 하는 것이 아닌 bitset stl를 활용하여 한번에 비트연산 처리를 함으로서 상수시간 내에 비트 연산을 처리할 수 있도록 구현하였다.

소스 코드

#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

vector< bitset<26> > input;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N, M;
    cin >> N >> M;

    for(int i=0; i<N; i++){
        string in;
        cin >> in;
        bitset<26> tmp; tmp.reset();

        for(int j=0; j<in.size(); j++){
            int idx = in[j]-'a';
            tmp.set(idx, true);
        }

        input.push_back(tmp);
    }

    bitset<26> mask;
    mask.set();

    for(int i=0; i<M; i++){
        int argc;
        char argv;
        cin >> argc >> argv;

        int idx = (int)(argv - 'a');
        if( argc == 1 ){
            // forget
            mask.set(idx, false);
        }else{
            // remember
            mask.set(idx, true);
        }

        int ans = 0;
        for(int j=0; j<input.size(); j++){
            bitset<26> s = input[j];
            bitset<26> res = s & mask;
            if( s == res )
                ans += 1;
        }
        cout << ans << '\n';

    }
    return 0;
}