[C++] 백준 11723번 집합

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

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
    
    string op;
    int m, x, ans = 0;
    cin >> m;
    while(m--){
        cin >> op;
        if(op == "all"){
            ans = ~(1 << 21);
        } else if(op == "empty"){
            ans = 0;
        } else{
            cin >> x;
            if(op == "add") {
                ans |= (1 << x);
            } else if(op == "remove"){
                ans &= ~(1 << x);
            } else if(op == "toggle"){
                ans ^= (1 << x);
            } else if(op == "check"){
                cout << ((ans & (1 << x)) ? 1 : 0) << "\n";
            }
        }
    }
    
    return 0;
}

풀이

vector를 쓰면 시간 초과가 발생한다. 대신 비트마스킹을 이용하여 x번째 비트에 1 또는 0을 저장한다.

비트 연산

• & : 둘 다 1이면 결과 1, 그 외에는 0 1010 & 0011 = 0010
• | : 둘 다 0이면 결과 0, 그 외에는 1 1010 | 0011 = 1011
• ^ : 하나만 1이면 결과 1, 그 외에는 0 1010 ^ 0011 = 1001
• ~ : 1과 0을 반대로 ~(1010) = 0101

• add x: S에 x를 추가한다.
  ➡️ 기존 집합 ans와 x번째 비트만 1이고 나머지는 0인 수에 | 연산 적용
• remove x: S에서 x를 제거한다.
  ➡️ 기존 집합 ans와 x번째 비트만 0이고 나머지는 1인 수에 & 연산 적용
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다.
  ➡️ 기존 집합 ans와 x번째 비트만 1이고 나머지는 0인 수에 & 연산 적용
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.
  ➡️ 기존 집합 ans와 x번째 비트만 1이고 나머지는 0인 수에 ^ 연산 적용
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
  ➡️ 모든 비트가 1인 수
• empty: S를 공집합으로 바꾼다.
  ➡️ 모든 비트가 0인 수 = 0