[BOJ/C++] 집합(11723번)

1. 개요

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

11723번: 집합

1-1. 설명

비어있는 공집합 S가 주어졌을때, 원소 추가, 제거, 체크, 토글 등 여러 연산들을 수행하는 프로그램을 작성한다. 자세한 연산은 위의 링크를 참고한다. 

1-2. 제한 사항

 - 첫 줄에 수행해야 하는 연산 수 M이 주어지며, M은 1 이상 3,000,000 이하

 - 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한줄에 하나씩 주어짐

2. 구현

2-1. 풀이

메모리가 매우 한정적이므, 비트마스킹을 이용해 풀었다. 

2-2. 코드 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

    int M, S = 0, inputNum;
    string inputStr;
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> inputStr;
        if (inputStr == "all") {
            S = (1 << 20) - 1;
            continue;
        }
        else if (inputStr == "empty") {
            S = 0;
            continue;
        }
        cin >> inputNum;
        inputNum -= 1;
        if (inputStr == "add") S |= (1 << inputNum);
        else if (inputStr == "remove") S &= ~(1 << inputNum);
        else if (inputStr == "check") cout << ((S & (1 << inputNum)) ? '1' : '0') << "\n";
        else if (inputStr == "toggle") S ^= (1 << inputNum);
    }
    return 0;
}