[BOJ/Gold 4] 백준 18119 단어 암기(C++)

문제 링크

https://www.acmicpc.net/problem/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

알고리즘 분류

• 비트마스킹

풀이

우선 각 단어마다 갖고 있는 알파벳의 개수는 상관없다. 따라서 각 단어마다 가지고 있는 알파벳을 비트마스킹을 통해 비트 집합에 저장한다.

그리고 준석이가 기억하고 있는 알파벳을 비트 집합 K로 관리한다. K가 0이면 모든 알파벳을 다 기억하고 있는 상태이다.

그리고 M개의 쿼리문을 받아 알파벳을 잊으면 해당 알파벳에 해당하는 번호를 추가한다. 예를 들어 b를 잊어버리면 K |= (1 << 2)로 두 번째 비트를 1로 변경한다.

다음으로 N개의 비트 집합과 비교하여 i번째 비트 집합에 K가 있는지 확인한다. 결과가 true라면 K가 없다는 뜻이다. 왜냐하면 예를 들면 b가 있다면 2번째 비트가 0이고, 없다면 1이기 때문이다.

마지막으로 결과가 false인 경우, 즉 완전히 알고 있는 단어의 개수를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, K, O;
char X;
string S;
vector<int> Vec;
int Answer;

void settings() {
    Answer = 0;
    if (O == 1) {
        K |= (1 << (X - 'a'));
    }
    else if (O == 2) {
        K &= ~(1 << (X - 'a'));
    }
    for (int i = 0; i < (int)Vec.size(); i++) {
        int Now = Vec[i];
        if (K & Now) {
            Answer++;
        }
    }
}

void find_Answer() {
    cout << N - Answer << "\n";
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> S;
        int T = 0;
        for (int i = 0; i < (int)S.size(); i++) {
            T |= (1 << (S[i] - 'a'));
        }
        Vec.push_back(T);
    }
    while (M--) {
        cin >> O >> X;
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}