백준[C++] 11732 집합

<조건 분석>

1. 처음엔 unordered_set으로 접근했음.

 

2. M은 최대 300만. unordered_set의 호출의 평균 연산이 2000cycle 정도임.

 

3. 3,000,000 * 2000 = 60억 cycle. cpu가 3GHz일 때, 약 2초정도 걸림.

 

4. 시간 제한은 1.5초이니 시간초과가 되어버림.

 

5. x가 20 이하의 자연수이니 int라는 하나의 정수 비트 안에 집합을 모두 담을 수 있음.

 

<문제 해결 포인트>

1. Map이나 Set같은 STL 자료구조로 해결하는 것이 아닌 문제의 x 정수 값을 보고 집합을 생각해 비트마스킹을 떠올려야 함.

 

2. check와 같은 경우에는 &= ~() 로, toggle과 같은 경우에는 XOR연산자인 ^=로 해결하면 됨.

 

#include <bits/stdc++.h>
using namespace std;

int bit = 0;

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

    
    int cnt;
    cin >> cnt;

    while (cnt--)
    {
        string text;
        int temp;
        cin >> text;

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

    return 0;
}