[백준 11723] 집합

🔗알고리즘 문제

실버5 문제이지만 생각하기 조금 복잡했던 문제 그래도 나름 깔끔하게 잘 푼 것 같다.

문제 분석

이 문제는 간단하게 집합 하나를 구현해내는 문제이다.

알고리즘 설계

300만이라는 큰 수의 연산을 모두 처리해야 하기에 자료구조를 사용하면 시간초과가 날 것 같았다. 고민해본 결과 간단한 집합 구현이라면 비트마스킹으로 처리할 수 있을 것 같아 비트마스킹을 이용해 구현할 수 있었다.

코드

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int m;
    int set = 0;

    cin >> m;

    for(int i = 0; i < m; i++){
        string order;
        int n;

        cin >> order;

        if(order == "add"){
            cin >> n;
            set = set | (1 << n);
        }
        else if(order == "remove"){
            cin >> n;
            set = set & ~(1 << n);
        }
        else if(order == "check"){
            cin >> n;
            cout << (set >> n) % 2 << "\n";
        }
        else if(order == "toggle"){
            cin >> n;
            set = set ^ (1 << n);
        }
        else if(order == "all"){
            set = (1 << 21) - 1;
        }
        else if(order == "empty"){
            set = 0;
        }
    }
}