백준 18119 단어암기

비트마스크 문제중에 쉬운편이었다. 

 

풀이방법은 
1. 단어를 비트마스킹해서 비트로 표현한다
2. 비트로 이루어진 온전한 알파벳판을 만든다 ex) a, b 만 있는 판은 -> 00000011 이런식으로
3. 1번케이스와 2번 케이스를 나누어 구현한다
3-1. 1번케이스의 경우 XOR 연산( 둘중 하나만 1일경우 1 )을 이용해 해당 알파벳 비트를 0으로 만든다
3-2. 2번케이스의 경우 OR연산( 둘중 하나라도 1일경우 1 )을 사용해 해당 알파벳 비트를 1로 만든다
4. 이렇게 만들어진 알파벳판과 본래의 단어비트를 &연산 ( 둘 다 1이여야 1 )한 값이 본래의 단어비트와 같은지 확인한다
5. 같을경우 cnt를 증가시켜서 갯수를 세어준다

 

로 단어를 비트로 바꾸고 비트연산을 할 줄 알면 풀 수 있는 문제였다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10000];
int alphabet =0;

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n >> m;
    //알파벳판
    for (int i = 0; i < 26; i++){
        alphabet |= (1 << i);
    }
    //단어를 비트마스킹함
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
      
        for(int j=0; j<str.size(); j++){
            int num;
            num = str[j] - 'a';
            
            arr[i] |= (1 << num);
            
        }

    }
    
    for(int i=0; i<m; i++){
        int cnt =0;
        int num;
        char alpha;
        cin >> num >> alpha;
        int alphaNum = alpha - 'a';
        if(num == 1){
            // 알파벳 잊기
            alphabet ^= (1<<alphaNum);
        }else{
            // 알파벳 기억하기
            alphabet |= (1<<alphaNum);
        }
        for(int j=0; j<n; j++){
            
            // 원래 단어 알파벳 보유 확인
            if((arr[j] & alphabet) == arr[j]){
                cnt++;
            }
        }
        
        cout << cnt << endl;
        
    }
    
}