[BOJ] #11723 집합

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

11723번: 집합

---

난이도 자체는 단순히 구현만 하면 되는 문제이기에 그리 어려운것은 없었지만, 처음에 문제 접근을 잘못 하면서 시간초과가 났고, 그로 인해 조금 헤맸다. 처음엔 단순히 vector에서 find로 인덱스를 찾고 뭐 그런 방식으로 풀었는데, 제시되는 테스트케이스가 최대 3,000,000이고, find의 시간복잡도가 O(N)이니까, 결국 O(N^2)가 된다. 시간초과가 날수밖에 없는 풀이법인 것이다. 

결국 그 방법 말고 비트마스킹을 이용해서 풀어야 시간 초과도 안나는데, 처음엔 저게 뭔가 했는데 찾아보고 나니까 아는 개념이었다. 용어만 몰랐던 것... 만약에 이런 문제가 실제로 코테에서 나왔다고 치면 실전에서는 백퍼 못풀었을것이다. 문제를 딱 보고 바로 어떤 방식으로 접근해야 하는지 아는것도 능력인듯 하다. 심지어 실전 코테에서는 이것보다 훨씬 어려운 문제가 나올텐데 말이다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

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

    int M;
    cin >> M;

    /*vector<int> v;

    while(M-->0) {
        string s;
        int n;

        cin >> s;

        if (s.compare("add") == 0) {
            cin >> n;
            v.push_back(n);
        }
        else if (s.compare("remove") == 0) {
            cin >> n;

            if (find(v.begin(), v.end(), n) == v.end()) continue;
            else v.erase(find(v.begin(), v.end(), n));
        }
        else if (s.compare("check") == 0) {
            cin >> n;
            
            if (find(v.begin(), v.end(), n) == v.end()) cout << 0 << '\n';
            else cout << 1 << '\n';
        }
        else if (s.compare("toggle") == 0) {
            cin >> n;

            if (find(v.begin(), v.end(), n) == v.end()) v.push_back(n);
            else v.erase(find(v.begin(), v.end(), n));
        }
        else if (s.compare("all") == 0) {
            v.clear();

            for (int i=1; i<=20; i++) v.push_back(i);
        }
        else if (s.compare("empty") == 0) v.clear();
     }
     비트마스킹이 뭐길래 했는데,,, 시간초과가 날수밖에 없는 구조
     이따구로 풀면 안되는 문제다
     */

    int arr[21] = { 0 };
    while(M-->0) {
        string s;
        int n;
        cin >> s;

        if (s.compare("add") == 0) {
            cin >> n;
            arr[n] = 1;
        }
        else if (s.compare("remove") == 0) {
            cin >> n;
            arr[n] = 0;
        }
        else if (s.compare("check") == 0) {
            cin >> n;

            if (arr[n] == 1) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else if (s.compare("toggle") == 0) {
            cin >> n;

            if (arr[n] == 1) arr[n] = 0;
            else arr[n] = 1;
        }
        else if (s.compare("all") == 0) {
            for (int i=0; i<21; i++) arr[i] = 1;
        }
        else if (s.compare("empty") == 0) {
            for (int i=0; i<21; i++) arr[i] = 0;
        }
    }

    return 0;
}