BOJ 11723 - 집합 / C++

문제 링크 : https://www.acmicpc.net/problem/11723

11723번: 집합

 

 

문제 풀이

실제 set을 쓰면 시간 초과가 나기 때문에 모든 함수를 구현해준다.

배열을 사용하며 입출력 시간도

ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);

를 통해 빠르게 만들어주어야 통과할 수 있다.

 

 

소스 코드

구현 풀이

#include <iostream>
#include <string>
using namespace std;
int arr[21] = { 0, };

void add(int x) {
    arr[x] = 1;
}

void remove(int x){
    arr[x] = 0;
}

void check(int x){
    if(arr[x] == 1){
        cout << 1 << '\n';
    }
    else {
        cout << 0 << '\n';
    }
}

void toggle(int x){
    if(arr[x] == 1) {
        arr[x] = 0;
    }
    else {
        arr[x] = 1;
    }
}

void clear(){
    for(int i=1; i<=20; i++){
        arr[i] = 0;
    }
}

void all(){
    for(int i=1; i<=20; i++){
        arr[i] = 1;
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        string str;
        cin >> str;

        if(str == "all" || str == "empty"){
            if(str == "all"){
                all();
            }
            else{
                clear();
            }
        }
        else {
            int x;
            cin >> x;
            if(str == "add") add(x);
            else if(str == "check") check(x);
            else if(str == "remove") remove(x);
            else if(str == "toggle") toggle(x);
        }
    }
}

비트마스크 풀이

#include <iostream>
#include <string>
using namespace std;
int BIT = 0;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        string str;
        cin >> str;

        if(str == "all" || str == "empty"){
            if(str == "all"){
                BIT = (1 << 21) - 1;
            }
            else{
                BIT = 0;
            }
        }
        else {
            int x;
            cin >> x;
            if(str == "add"){
                BIT |= (1 << x);
            }
            else if(str == "check"){
                if(BIT & (1 << x)) cout << 1 << '\n';
                else cout << 0 << '\n';
            }
            else if(str == "remove"){
                BIT &= ~(1 << x);
            }
            else if(str == "toggle"){
                BIT ^= (1 << x);
            }
        }
    }
}

 

시간 비교