문제 링크

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.


문제

준석이는 영어 단어를 외우려고 한다. 사전에는 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. 단어별로 사용된 알파벳을 기록해두고 기억하지 못하는 알파벳을 가지고 있다면 알지 못하는 단어라는 것을 확인할 수 있다. 그렇다면 알파벳 사용 여부를 어떻게 저장하고 비교할지를 생각해야 하는데 알파벳이 26개이므로 32비트 정수에 비트 플래그를 사용하여 기록하기로 했다. 만약 26칸짜리 배열을 사용하여 기록한다면 메모리를 과하게 사용하고 단어마다 26번씩 비교하는 과정에서 속도가 느려질 것이다.
  2. 다음 순서에 따라 구현하였다.
    1. 단어를 입력받고 단어에 포함된 알파벳에 해당하는 위치의 비트 플래그를 1로 설정한다.
    2. 입력받은 쿼리에 따라 기억하지 못하는 알파벳의 비트를 1, 기억하는 비트를 0으로 설정해준다.
    3. 모든 단어에 대해 AND 연산을 통해 기억하지 못하는 알파벳이 있는지 확인한다. 기억하지 못하는 알파벳이 없다면 해당 단어는 알고 있는 단어가 될 것이다.
  3. 그럭저럭 빠른 속도로 실행되어 만족스럽긴 하지만 애초에 시간제한이 4초씩이나 주어지고 메모리 제한도 1GB이기 때문에 비트 플래그를 사용하지 않고 배열을 사용해도 통과하는 데는 문제가 없었을 것 같다.


소스 코드

#include <iostream>
#include <string>

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    int n, m;
    std::string s;
    unsigned int wordBits[10000] = {0, };
    unsigned int unknownAlpha = 0;

    std::cin >> n >> m;
    
    s.reserve(1000);
    for (int i = 0; i < n; ++i) {
        std::cin >> s;

        for (unsigned int k = 0; k < s.length(); ++k) {
            wordBits[i] |= (1 << (s[k] - 'a'));
        }
    }
    
    for (int i = 0; i < m; ++i) {
        char query, alphabet;
        std::cin >> query >> alphabet;

        alphabet -= 'a';
        if (query == '1') {
            unknownAlpha |= (1 << alphabet);
        } else {
            unknownAlpha &= ~(1 << alphabet);
        }

        int knownCount = 0;
        for (int i = 0; i < n; ++i) {
            if ((wordBits[i] & unknownAlpha) == 0) {
                ++knownCount;
            }
        }

        std::cout << knownCount << '\n';
    }

    return 0;
}