[백준/c++] 11723번: 집합

 

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

11723번: 집합

 

 

 

[시간 초과 - set 사용]

사실 시간초과 나올 줄 알았다.. 후^^

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m;
    set<int> s;
    cin >> m;
    while(m--){
        string str;
        int n;
        cin >> str;
        if(str == "add"){
            cin >> n;
            s.insert(n);
        }else if(str == "remove"){
            cin >> n;
            s.erase(n);
        }else if(str == "check"){
            cin >> n;
            if(s.count(n) != 0) cout << 1 << '\n';
            else                cout << 0 << '\n';
        }else if(str == "toggle"){
            cin >> n;
            if(s.count(n) != 0) s.erase(n);
            else                s.insert(n);
        }else if(str == "all"){
            s.clear();
            for(int i=1; i<=20; i++) s.insert(i);
        }else if(str == "empty"){
            s.clear();
        }
    }
    return 0;
}

 

[비트 마스킹 코드]

다른 사람의 코드를 보고 알 수 있었다

(1<<n)은 n번째 자릿수라고 보고

S 집합에 i라는 수가 들어오면 i번째가 1이 된다. 즉, i번째 수가 1이 되면 S 집합에 i가 들어온 것으로 친다.

 

ADD: n번째 자릿수를 1로 바꾼다

bit = bit | (1<<n)

//bit = 0, n = 2
//bit = 0 | 100 = 100
//bit = 100, n = 3
//bit = 100 | 1000 = 1100

 

REMOVE: n번째 자릿수를 0으로 바꾼다

bit = bit & ~(1<<n)

//bit = 1100, n = 3
//bit = 1100 & 0111 = 0100

 

CHECK: n번째 자릿수가 있는지(1)/없는지(0)

bit = bit & (1<<n)

//bit = 0100, n = 4
//bit = 0100 & 10000 = 0
//bit = 0100, n = 2
//bit = 0100 & 100 = 1

 

TOGGLE: n번째 자릿수 flip (1->0, 0->1)

bit = bit ^ (1<<n)

//bit = 0100, n = 4
//bit = 00100 ^ 10000 = 10100

 

ALL: 모두 1로 변경 (1~20이므로 21에서 1 빼면 20개가 모두 1이 된다)

bit = (1<<21) - 1

//bit = 1000 
//bit = 1000 - 1 = 111

 

EMPTY: 초기화

bit = 0

 

 

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m;
    cin >> m;
    string str;
    int n, bit = 0;
    while(m--){
        cin >> str;
        if(str == "add"){
            cin >> n;
            bit |= (1<<n); //n번째 자리수를 1로 바꾼다
            //bit = 100
        }else if(str == "remove"){
            cin >> n;
            bit &= ~(1<<n);
            //bit = 100 & 001 = 000 //해당 수 없애기
        }else if(str == "check"){
            cin >> n;
            if(bit & (1<<n)) cout << 1 << '\n';
            else             cout << 0 << '\n';
            //bit = 100 & 100 = 1
            //bit = 100 & 101 = 0
        }else if(str == "toggle"){
            cin >> n;
            bit ^= (1<<n);
            //bit = 100 ^ 100 = 0 //XOR는 다르면 1
        }else if(str == "all"){
            bit = (1<<21) - 1;
            //1000 - 1 = 111
        }else if(str == "empty"){
            bit = 0;
            //초기화
        }
    }
    return 0;
}