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

www.acmicpc.net/problem/18119

18119번: 단어 암기

 

 

 

알고리즘 종류

구현

문자열

 

 

사고 과정

비트마스크를 사용하지 않고 구현하면 제출이 되었지만, 시간이 오래 걸렸습니다. 비트마스크를 사용하면 어떤 알파벳이 있는지 쉽게 알 수 있습니다.

 

1. 처음에는 모든 알파벳을 기억한다고 했으니 or 연산으로 모든 알파벳을 기억합니다.

 

2. 단어를 입력받으면, dict 배열에서 단어의 문자를 or 연산으로 기억합니다.

 

3. 쿼리르 입력 받으면, And와 or 연산을 이용해서 잊어버리거나 기억을 합니다. 그리고 현재 기억하고 있는 알바벳들(remember)와 단어의 문자들이 저장된 dict을 And로 비교해서 모두 읽을 수 있는지 확인합니다.

 

 

 

구현(C++)

#include <iostream>
#include <string>
 
using namespace std;
 
int n, m;
int remember = 0;
 
int dict[10001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> m;
    
    // or 연산으로 모든 알파벳을 기억합니다. 
    for (int i = 0; i < 26; i++) {
        remember |= (1 << i);
    }
    
    string str;
    for (int i = 0; i < n; i++) { // bring a word
        cin >> str;
 
        for (int j = 0; j < str.size(); j++) { // 단어의 알파벳을 or 연산으로 저장합니다. 
            char c = str[j]; 
            dict[i] |= (1 << (c-'a'));
        }
    }
 
    int o;
    char x;
    for (int i = 0; i < m; i++) {
        int cnt = 0;
        cin >> o >> x;
 
        if(o==1) remember &= ~(1 << (x -'a')); // ~ 으로 반전시켜주고 &으로 제외시켜줍니다. 
        else remember |= (1 << (x -'a')); // or 연산으로 더해줍니다. 
 
        for (int j = 0; j < n; j++) {
            if ((dict[j] & remember) == dict[j]) // dict에 있는 단어의 알파벳과 현재 기억하고 있는 알파벳들을 비교합니다. 
               cnt++;
        }
        cout << cnt << "\n";
    }
}

 

 

 

시행착오