[백준] 18119. 단어 암기 - C++

[Gold IV]

 

https://www.acmicpc.net/problem/18119

18119번: 단어 암기

 

풀이

원래 Bitmask 문제를 제일 까다로워하고, 익숙치 않아 했는데,

점점 풀 만해지는 것 같다. ^ㅁ^!

 

이 문제는 각각의 알파벳(a, b, c, d, ..., x, y, z)의 기억 여부를, 비트마스킹으로 저장하는 것이 핵심이다.

32 bit의 int형 숫자를 이용해, 26개의 알파벳 각각의 기억 여부를 저장한다.

ex) 00000000 00000000 00001000 00010001 => a, e, l 기억 중.

 

---

우선, 처음에는 알파벳 26개를 모두 기억하고 있으므로, 26개까지 1로 만든다. (line 18)

s = 00000011 11111111 11111111 11111111

 

또한, 입력되는 N개의 문자열도 bitmasking을 통해 저장한다.

우리가 필요한 것은, 각각의 알파벳의 개수가 아닌, 그 단어에 어떤 알파벳이 존재하는 지 이므로, 존재하는 알파벳만을 1로 만든다.

그 숫자를 list vector에 int형으로 저장.

ex) apple -> 00000000 00000000 10001000 00010001

 

그리고 M회 query를 실행한다.

command == 1 로 알파벳을 잊어야 한다면, s &= ~(1 << (ch - 'a')); (line 40)

command == 2 로 알파벳을 기억해야 한다면, s |= (1 << (ch - 'a')); (line 43)

으로 무슨 알파벳을 기억하고 있는 지 기록하고,

그 이후, 저장된 모든 문자열에 대하여 s 와 AND 연산을 통해,

그 단어의 모든 알파벳을 기록하고 있는 지 확인하여, 기억하는 단어의 수를 센다.

((s & list[j]) == list[j], line 47)

예를 들어, 첫 쿼리에서 1 l 이라는 입력이 들어온다면, 알파벳 l 을 잊어야 하므로,

s = 00000011 11111111 11110111 11111111 이 될 것이고,

이 때 apple 은 00000000 00000000 10001000 00010001 이다.

이 두 가지를 AND 연산 한다면, 아래와 같다.

	00000011 11111111 11110111 11111111
&	00000000 00000000 10001000 00010001
---------------------------------------
	00000000 00000000 10000000 00010001

AND 연산의 결과는 apple 을 bit로 표현한 결과와 달라졌으므로, ((s & list[j]) == list[j])

apple 이라는 단어를 기억하지 못하는 것과 같다. 이 과정을 모든 단어에 대해 반복한다.

 

AC.

#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);

using namespace std;

int main() {
    init;

    int N, M;
    cin >> N >> M;
    int s = 0;

    // 알파벳 26개 기억. (기억 -> 0 / 잊음 -> 1)
    s |= (1 << 26) - 1;

    // 문자열을 bitmasking하여 저장 (알파벳의 개수는 상관없으므로, 무슨 알파벳이 들어왔는지만.)
    vector<int> list;
    string temp = "";
    for (int i = 0; i < N; i++) {
        cin >> temp;
        int t = 0;
        for (int j = 0; j < temp.length(); j++) {
            t |= (1 << (temp[j] - 'a'));
        }
        list.push_back(t);
    }

    // 쿼리 실행
    int command;
    char ch;
    for (int i = 0; i < M; i++) {
        cin >> command >> ch;
        int cnt = 0;
        if (command == 1) {
            // 입력된 문자 잊기. (bitmask 삭제)
            s &= ~(1 << (ch - 'a'));
        } else {  // command == 2
            // 입력된 문자 기억하기. (bitmask 추가)
            s |= (1 << (ch - 'a'));
        }

        for (int j = 0; j < N; j++) {
            if ((s & list[j]) == list[j]) {
                cnt++;
            }
        }
        cout << cnt << "\n";
    }
}