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

🌱 문제

🌱 풀이

• 비트마스크 문제이다
• 처음엔 벡터 이용해서 풀었는데 어디서 틀린지 모르겠다....

(1<<x)로 통일한 풀이

• add 연산: result = result|(1<<x)
• remove 연산: result = result&~(1<<x)
• check 연산: result = result&(1<<x)
• toggle 연산: result= result^(1<<x)
• all 연산: result=pow(2,21)-1
• empty 연산: reuslt = 0

💡 비트마스크

• 비트마스크는 사실 브루트포스 보다는 다이나믹 프로그래밍 에서 자주 사용한다.
• 그러나 브루트포스는 비트마스크로 풀 수도 지만 재귀로 푸는게 좋다.

비트마스크 장점

• 정수를 사용한다.
• 삽입, 삭제, check, toggle 등의 모든 연산이 O(1)이다.

비트마스크 단점

• 정수를 사용하는게 장점이자 단점이다.
• 정수는 주로 32비트 또는 64비트를 사용하는데 32비트일 경우 정수는 0~ 2^32-1 값 까지 가질 수 있고, 64비트일 경우 0 ~ 2^64-1 까지 가질 수 있으므로 각각 집합의 갯수가 0~31개 까지, 0~63개 까지만 저장할 수 있다.

🌱 코드

• 실패한 코드 (왜 틀렸는지 못알아냈다. 런타임 오류라는데 왜지 ...)

//11723번: 집합
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    string str;
    int x;
    cin>>m;
    for(int i=0; i<m; i++){
        cin>>str;
        if(str=="add"){
            cin>>x;
            auto it=find(v.begin(),v.end(),x);
            if(it==v.end()) // 없는 경우만 push
            v.push_back(x);
        }
        else if(str=="remove"){
            cin>>x;
            auto it=find(v.begin(),v.end(),x);
            if(it!=v.end()) //있는 경우
            v.erase(v.begin()+(*it)-1);
        }
        else if(str=="check"){
            cin>>x;
             auto it=find(v.begin(),v.end(),x);
            if(it!=v.end())
            cout<<1<<"\n";
            else
            cout<<0<<"\n";
        }
        else if(str=="toggle"){
            cin>>x;
            auto it=find(v.begin(),v.end(),x);
            if(it!=v.end())
             v.erase(v.begin()+(*it)-1);
            else
            v.push_back(x);
        }
        else if(str=="all"){
            vector <int>().swap(v); 
            for(int i=1; i<=20; i++){
                v.push_back(i);
            }
        }else{
             vector <int>().swap(v); 
        }

        // for(int i=0; i<v.size(); i++){
        //     cout<<v[i]<<" ";
        // }
        // cout<<endl;
    }
}
// 이 코드 왜 런타임에러인지 모르겠다 

• 정답 코드

//11723번: 집합
#include <iostream>
#include <cmath>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int result=0;
    int m;
    int x;
    string s;
    cin>>m;
    while(m--){
        cin>>s;
        if(s=="add"){
            cin>>x;
            result= result|(1<<x);
        }else if(s=="remove"){
            cin>>x;
            result=result&~(1<<x);
            
        }else if(s=="check"){
            cin>>x;
            bool check=result&(1<<x);
            if(check==true)
            cout<<1<<"\n";
            else
            cout<<0<<"\n";
        }else if(s=="toggle"){
            cin>>x;
            result=result^(1<<x);
        }else if(s=="all"){
            result=pow(2,21)-1;
        }else{
            result=0;
        }

    }
}