(매일 BOJ) C++ 11723번 집합

이번 문제는 11723번 집합문제이다.

접근법

1. 원소 범위가 작다 → 배열 또는 비트마스크 사용 가능

• 원소 범위: 1 ≤ x ≤ 20
• 집합 전체를 표현하는 데 21칸짜리 배열 또는 정수형 1개로 충분함

---

2. 연산이 많다 → O(1) 시간 복잡도 필수

• find(), erase()가 포함된 STL vector나 set 사용 시 시간 초과 발생
• 모든 연산을 상수 시간에 처리해야 함

 

1차 코드

int 형의 vector를 사용해서 find, erase 등의 메서드를 사용하여 구현 > 시간복잡도 O(n) TLE

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    long long num;
    cin >> num;
    vector<int> v;

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

        if(str == "add"){
            v.push_back(n);

        }
        else if(str == "remove"){
        auto f = find(v.begin(),v.end(),n);
            if (f != v.end()){
                v.erase(f);
            }
        }
        else if(str == "check"){
            auto f = find(v.begin(),v.end(),n);
            if (f != v.end()) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else if(str == "toggle"){
            auto f = find(v.begin(),v.end(),n);
            if (f != v.end()){
                v.erase(f);
            }
            else{
                v.push_back(n);
            }
        }
        else if(str == "all"){
            vector<int> temp;
            for(int i = 1; i <= 20; i++){
                temp.push_back(i);
            }
            v = temp;
        }
        else if(str == "empty"){
            v = {};
        }
    }
}

2차코드

1차코드에서 처리해야 하는 반복횟수로 인한 TLE를 해결하기 위해 bool 자료형의 vector 사용

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    long long num;
    cin >> num;
    vector<bool> v(21);

    for(int i = 0; i < num; i++){
        string str;
        int n;
        cin >> str;
        if(str != "all" && str != "empty"){
            cin >> n;
        }
        

        if(str == "add"){
            v[n] = true;

        }
        else if(str == "remove"){
            if (v[n] == true){
                v[n] = false;
            }
        }
        else if(str == "check"){
            if (v[n] == true) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else if(str == "toggle"){
            if (v[n] == true){
                v[n] = false;
            }
            else{
                v[n] = true;
            }
        }
        else if(str == "all"){
            for(int i = 1; i <= 20; i++ ){
                v[i] = true;
            }
        }
        else if(str == "empty"){
            for (int i = 1; i <= 20; i++){
                v[i] = false;
            }
        }
    }
}