[백준] 18119번 단어암기 (C++)

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

 

 

이 문제는 N개의 문자열과 M개의 쿼리가 존재할때 각 쿼리에 맞는 수행을 하는 문제이다.

 

초기에 준석이는 모든 알파벳을 기억하고 있으며 1번 쿼리와 문자가 주어지면 그 문자를 잊고

2번 쿼리와 문자가 주어지면 그 문자를 다시 기억시킨다.

 

N의 크기는 10^4 이며 M의 크기는 5 * 10^5이다. 제한시간은 4초로 4 * 10^8이다

 

일단 알파벳의 개수를 확인하기 위해 배열을 N만큼은 확정적으로 순회해야된다고 생각하였다.

 

결국 어떻게 풀어야할지 감을 못잡아서 풀이를 확인해 보았다.

 

이 문제는 간단하게 비트마스킹으로 쉽게 풀 수 있다.

알파벳은 총 26개이다 즉 내가 알고있는 알파벳은 1, 모르는 알파벳은 0으로 설정하면 26개의 비트를 사용하여 판별할 수 있다.

 

 

만약 내가 알고있는 비트를 a 라고 하고 N만큼 순회하여 &(and) 연산을 했을때 해당 문자의 비트가 나온다면 이는 그 단어를 완전히 아는 것이기 때문에 +1을 해주며 아닌 경우 모르는 문자이기 때문에 세주지 않는다.

 

또한 알파벳을 기억할때는 알파벳 위치만큼 왼쪽 시프트 연산을 하고 or연산을 하여 해당 비트를 1로 만든다.

 

하지만 알파벳을 잊으려고 할때는 알파벳 위치만큼 왼쪽 시프트 연산을 하고 해당 비트를 NOT으로 반전시켜 &(and) 연산을 하여 해당 비트만 0으로 만든다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M;
vector<int> v;

void Print() {
    for(auto it : v) {
        cout << it << endl;
    }
}

void solve() {
    int bits = (1 << 26) - 1;

    for(int i = 0; i < M; i++) {
        int a;
        char b;
        int cnt = 0;
        cin >> a >> b;

        if(a == 1) {        // 단어를 잊음
            bits &= ~(1 << (b - 'a'));
        }
        else {
            bits |= (1 << (b - 'a'));
        }

        for(int j = 0; j < N; j++) {
            if((v[j] & bits) == v[j]) {
                cnt++;
            }
        }

        cout << cnt << endl;
    }
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        string s;
        int a = 0;
        cin >> s;

        for(int j = 0; j < s.size(); j++) {
            a |= (1 << (s[j] - 'a'));
        }

        v.push_back(a);
    }
}

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

    input();
    solve();
}

 

 

회고록

비트마스킹.... 쉽사리 떠오르지 않는 테크닉인것 같다 더욱 이러한 비슷한 유형의 문제를 풀며 바로 떠올릴 수 있도록 연습만이 답인것 같다. 앞으로 못푼 문제들은 다시한번씩 풀어봐야 계속해서 기억이 날 것 같다.