백준 11723번: 집합

문제

문제 바로가기> 백준 11723번: 집합

풀이

비트마스킹을 이용해서 푸는 문제다! 비트가 켜져있으면(1) 해당 원소가 집합 안에 존재하는 것이고, 비트가 꺼져있으면(0) 해당 원소가 집합에 존재하지 않음을 의미하는 것이다. 아래서 사용하는 연산은 모두 bit 연산들이다 :)

add: 해당 위치(num)의 원소를 켜주기 위해 shift(해당 위치로 이동), OR(비트를 킴) 연산을 이용한다!
remove: 해당 위치(num)의 원소를 꺼주기 위해 shift(해당 위치로 이동), ~/AND(해당 원소만 0으로 만들어서 & = 제거) 연산을 이용한다!
check: 해당 위치(num)의 원소가 켜져있는지 확인하기 위해 shift(해당 위치로 이동), AND(비트가 켜져있는지 확인) 연산을 이용한다!
toggle: 해당 위치(num)의 원소가 있으면 제거하고, 없으면 추가하기위해 shift(해당 위치로 이동), XOR(1^0=1, 1^1=0) 연산을 이용한다!
all: 20개의 원소를 모두 켜주기 위해 shift(<<21)한 후 -1을 해준다! ex) 1<<4(4만큼 shift) = 1000 , 1000-1 = 0111(3개의 원소 켜짐)
empty: 집합을 비우는 것이므로 bit를 0으로 설정해주면 된다!

#include<iostream>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int M; cin >> M;
    string oper;
    int num, SET=0;
    while (M--){
        cin >> oper;
        if(oper=="all") SET = (1<<21)-1;
        else if(oper=="empty") SET = 0;
        else{
            cin >> num;
            if(oper=="add") SET|=(1<<num);
            else if(oper=="remove") SET&=~(1<<num);
            else if(oper=="check") {
                if(SET&(1<<num)) cout << 1 << '\n';
                else cout << 0 << '\n';
            }
            else if(oper=="toggle") SET^=(1<<num);
        }
    }
}