[C++] 백준 11723번: 집합

문제

난이도 : 실버 5
백준 11723번 : 집합

코드

#include <bits/stdc++.h>

using namespace std;

int M;
int S;

int main()
{
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> M;

    while (M--)
    {
        string input;
        int x;

        cin >> input;

        if (input == "add")
        {
            cin >> x;
            if(S & (1 << x - 1)) continue;
            S |= (1 << x - 1);
        }
        else if (input == "remove")
        {
            cin >> x;
            if (!(S & (1 << x - 1))) continue;

            S &= ~(1 << x - 1);
        }
        else if (input == "check")
        {
            cin >> x;
            if(S & (1 << x - 1)) cout << 1 << '\n';
			else cout << 0 << '\n';
        }
        else if (input == "toggle")
        {
            cin >> x;
            S ^= (1 << x - 1);
        }
        else if (input == "all")
        {
            S = (1 << 20) - 1;
        }
        else if (input == "empty")
        {
            S = 0;
        }
    }

    return 0;
}

설명

처음 문제를 보고 그냥 입력값에 따른 배열 인덱스만 건드리면 될 것 같아 풀었는데 바로 시간초과가 떴다.
시간이 흐르고 코딩테스트 강의에서 비트마스킹 강의를 듣고 난 후에 아 비트마스킹으로 푸는 문제이구나라고 느꼈다.
언젠가 비트마스킹도 블로그에 정리해야겠다. 아무튼 비트마스킹의 핵심은 크기 20의 배열을 하나의 숫자로 나타내어 자릿수가 배열의 인덱스의 역할을 하는 것으로 이해해야 함.
그리고 비트마스킹에서 주로 사용하는 연산들도 외워야 함. 예를 들어 idx번째 비트가 1인지 확인하기(if(S & (1 « x - 1)) 등

결과