백준 11723 집합 c++ [컴공과고씨]

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

11723번: 집합

이 문제는 비트 연산 이용하는 문제로 나는 처음에 벡터를 이용해 풀어서 시간초과가 났다.

비트연산을 모르는 사람이 있다면 https://hagisilecoding.tistory.com/54 여기서 공부를 하고 오면 쉽게 이해할 수 있다.

 

단계별 문제 풀이

1.  |= (1<<n) 로 원하는 원소 더해주고

2. &= ~(1<<n) 을 이용하여 원소 제거

3. if(s&(1<<n)) 를 이용해서 check 구현

4. s ^= (1<<n) 를 이용해서 toggle 구현

5. s = (1<<21) - 1 을 이용해서 all 구현

6. s = 0 -> 공집합

 

 

전체코드

#include <iostream>
#include <string>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    unsigned int s = 0;
    int m, n;
    string a ="";
    cin >> m;
    while(m--){
        cin >> a;
        if(a=="add"){
            cin >> n;
            s |= (1 << n);
        }else if(a == "remove"){
            cin >> n;
            s &= ~(1 << n);
        }else if(a== "check"){
            cin >> n;
            if(s & (1<<n)){
                cout << 1 << '\n';
            }else{
                cout << 0 << '\n';
            }
        }else if(a=="toggle"){
            cin >> n;
            s ^= (1<<n);
        }else if(a=="all"){
            s = (1 << 21) - 1;
        }else if(a == "empty"){
            s = 0;
        }
    }
    return 0;
} //비트연산자 공부 후 16min

체감 난이도	걸린시간	참고	사용 알고리즘, 문법
중	16min	비트 마스킹을 이용해야한다는 힌트를 보고 비트 마스킹을 해본적이 없어 비트 마스킹에 대해 공부 품	비트 마스킹