[BOJ] 11723 집합

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

11723번: 집합

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bit을 활용한 set 조작

 

---------------------------------------------------풀이----------------------------------------------------

 

원소의 개수가 총 20개밖에 안되므로 array를 활용하였다.

bool로 선언하여 존재하면 true, 없으면 false로 만들었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int main(void){
    FASTIO;
    int M;
    cin >> M;
    bool set[21] = {false, };
    while(M--){
        string cmd;
        cin >> cmd;
        int x;
        if(cmd == "add"){
            cin >> x;
            set[x] = true;
        }
        else if(cmd == "remove"){
            cin >> x;
            set[x] = false;
        }
        else if(cmd == "check"){
            cin >> x;
            cout << set[x] << "\n";
        }
        else if(cmd == "toggle"){
            cin >> x;
            set[x] ^= true;
        }
        else if(cmd == "all"){
            for(int i = 1; i <= 20; i++){
                set[i] = true;
            }
        }
        else if(cmd == "empty"){
            for(int i = 1; i <= 20; i++){
                set[i] = false;
            }
        }
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

비트마스킹을 사용하는 알고리즘으로 되어 있었다.

2^20은 integer 범위 안에 들어오므로 bit를 조작해서 표현하는 것이 더 빠를 것 같긴 하다.

all이나 emtpy같은 경우에 나는 array의 원소를 전부 true나 false로 만들어 주었지만,

비트마스킹을 활용한다면 0이나 1로 바꿔주면 빠르게 될 것이다.