백준 18119번 단어 암기 // C++

문제

단어 암기

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

 

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

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

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

 

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

입력

첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다.

 

다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다.

 

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

 

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

출력

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

---

풀이

일일히 find를 사용하면 시간 초과가 발생할 것이라 생각해 bit 연산을 사용하여 해결하였다.

 

각 문자열을 입력받아 문자열 상태가 아닌, 해당 문자열에 사용된 알파벳을 bit로 표현하여 int형 배열에 저장하였다.

 

bit 수가 1이라면 해당 알파벳을 사용, 0이라면 사용하지 않은 경우로 뒀다.

 

remember 변수는 현재 암기하고 있는 알파벳을 나타내기 위해 사용했으며, 처음에는 모든 알파벳을 기억하고 있기 때문에 초기화를 과정을 거쳤다.

 

각 알파벳을 암기하거나 잊었을 경우, 문자열과 remember에 & 연산을 수행하여 문자열 그대로가 나온다면 해당 문자열을 알고 있다는 뜻이다.

 

예를 들어 a~e까지의 알파벳만을 사용한다고 했을 때 remember 변수는 11111(63)이 된다.

단어 abc는 배열에 00111(7)로 저장되며, abc & remember = 00111(7)이기 때문에 abc와 연산 결과가 같아 해당 단어를 기억하고 있다는 것으로 볼 수 있다.

여기서 a 문자를 잊게 되면, remember 변수는 11110(62)가 되고, (abc & remember = 00110(6)) != abc이기 때문에 해당 단어를 기억할 수 없다.

---

코드

#include <iostream>
#include <string>

using namespace std;

int arr[10001] = { 0, };

int main() {
    int n, m;
    int remember = 0;

    cin >> n >> m;

    for (int i = 0; i < 26; i++) {
        remember = remember + (1 << i);
    }

    string temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        int cur;

        for (int j = 0; j < temp.size(); j++) { // 해당 문자열에 사용된 알파벳을 저장
            cur = temp[j] - 'a';
            arr[i] |= (1 << cur);
        }
    }

    int o;
    char x;

    for (int i = 0; i < m; i++) {
        int count = 0;
        cin >> o >> x;

        remember ^= (1 << (x - 'a'));

        for (int j = 0; j < n; j++) {
            if ((arr[j] & remember) == arr[j])
                count++;
        }
        cout << count << "\n";
    }

    return 0;
}