[BOJ] 백준 18119번 - 단어 암기 풀이

| |
백준 온라인 저지 백준 18119번 - 단어 암기 C++ 풀이


문제

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

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

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

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


입력

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

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

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

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


출력

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


풀이

떠올릴 수 있는 가장 간단한 방법은 매 순간마다 모든 문자열을 첫 글자부터 검사하는 것이다. 최악의 경우의 시간복잡도를 계산해보면 다음과 같다.

문자열의 최대 갯수 × 문자열의 최대 길이 × M의 최댓값

즉, 10,000 × 1,000 × 50,000 = 500,000,000,000

그러므로 O(NM) 알고리즘을 사용할 경우 문제에서 제시한 시간 제한인 4초 에 돌아가긴 커녕 400초 를 줘도 돌아갈지 의문이다. 따라서 정공법은 통하지 않으므로 비트마스킹 을 활용해야 한다.

하나의 배열에 문자열 대신 이 문자열이 알파벳 중 어떤 알파벳을 포함하고 있는지에 대한 정보만을 저장할 것이다. 비트마스킹을 이용할 경우 이 정보를 정수형으로 표현할 수 있다. 하나의 정수를 이진수로 생각하고, 해당 문자열이 n번째 알파벳을 포함하고 있을 경우 정수의 n번째 비트를 켜고, 아닐 경우 켜지 않는다. 따라서 문자열이 입력될 때마다 문자열을 검사하고 비트마스킹의 결괏값(정수형)을 vector 에 저장한다.

또, 자신이 기억하고 있는 알파벳 또한 비트마스킹을 이용해 나타낼 수 있다. 똑같이 n번째 문자열을 잊어버렸을 경우 n번째 비트를 켜고 아닐 경우 켜지 않는다.

단어를 알고 있는지에 대한 판별은 구현 방식에 따라 두가지로 나뉠 수 있다.


  • 자신이 기억하는 문자열 번호를 켰을 경우 다음을 만족해야 아는 단어이다.

    • AND(단어, 기억) == 단어

  • 자신이 잊어버린 문자열 번호를 켰을 경우 다음을 만족하면 모르는 단어이다.

    • AND(단어, 기억) == TRUE(0이 아니다)


그리고 소소한 팁으로 쿼리가 주어지는 과정에서 입력된 정수 o에 상관없이 단순히 문자 x에 대하여 비트를 토글해도 상관 없으므로 정수 o에 대한 조건문 처리를 생략할 수 있다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

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

    vector<int> strs(N);
    for(int i=0;i<N;i++){
        string s; cin>>s;
        for(char c:s) strs[i] |= (1<<(c-'a'));
    }

    int mem = 0;
    while(M--){
        int ans=0;
        char x;

        cin>>x>>x;
        mem ^= (1<<(x-'a'));

        for(int s:strs) if(s & mem) ans++;

        cout<<N-ans<<'\n';
    }

    return 0;
}
0%