백준 11723 (집합) c++

문제

11723번: 집합

 

집합 S에 다음과 같은 명령어를 m (m <= 30000000)번 실행하는 프로그램을 만드는 문제입니다.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

단순히 벡터에 수를 넣어줘서 해결하였지만 메모리 초과가 나왔습니다.

따라서 총 2가지 방법을 생각해 볼 수 있습니다.

 

1) x는 어차피 1 부터 20 까지 이므로 int arr[21]로 잡고 

만약 add 15 이면 arr[15] = 1 로 하고

remove 15이면 arr[15] = 0으로 하는 식으로 하는 겁니다.

 

2) bit mask로 해결하는 방법입니다.

x가 어차피 1부터 20까지 이기 때문에 

2^21 정도 bit를 사용하면 됩니다.

---

전체 코드입니다. (bit mask)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<int>v;
vector<int>::iterator it;
int bit;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    
    int m;
    cin >> m;
    while (m--) {
        string st;
        cin >> st;
        if (st == "add") {
            int a;
            cin >> a;
            bit |= (1 << a);
        }
        else if (st == "remove") {
            int a;
            cin >> a;
            bit &= ~(1 << a);
        }
        else if (st == "check") {
            int a;
            cin >> a;
            if (bit & (1<<a))
                cout << '1' << '\n';
            else cout << '0' << '\n';
        }
        else if (st == "toggle") {
            int a;
            cin >> a;
            if (bit & (1 << a)) {
                bit &= ~(1 << a);
            }
            else bit |= (1 << a);
        }
        else if (st == "all") {
            bit = (1 << 21) - 1;
        }
        else {
            bit = 0;
        }
    }
 
    return 0;
}