[백준] 11723 집합 c++

배열이나 set을 이용하여 문제를 해결할 수 있다.

주의해야할 사항은 시간초과와 메모리초과이다.

 

1. 시간초과

밑의 두가지 코드를 통해 해결한다.

ios_base::sync_with_stdio(false); // c의 stdio와 cpp의 iostream의 동기화를 해제해준다.

cin.tie(NULL); // 버퍼를 비워줌 cin와 cout을 독립적으로 만들어준다.

 

2. 메모리초과

결과값을 담아 마지막에 한번에 출력해주는 vector를 사용하면 메모리 초과가 난다. input stream / output stream은 별개이니 굳이 마지막에 모아서 결과를 출력하지 않아도 된다.

 

배열을 이용한 풀이

#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

vector<int> v(21); // index값 1-존재, 0-없음.

void init(){ // 1~20 초기화.
    for (int i = 1; i <= 20; i++){
        v[i] = 1;
    }
}

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

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

    int n,x;
    string type;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> type;
        if (type.compare("all") == 0) init();
        else if (type.compare("empty") == 0) arrEmpty();
        else{
            cin >> x;
            if (type.compare("add") == 0)
            {
                v[x] = 1;
            }
            if (type.compare("remove") == 0)
            {
                v[x] = 0;
            }
            if (type.compare("check") == 0)
            {
                v[x] == 1 ? cout << "1\n" : cout << "0\n";
            }
            if (type.compare("toggle") == 0)
            {
                v[x] == 1 ? v[x] = 0 : v[x] = 1;
            }
        }
    }
}

 

set을 이용한 풀이

#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

set<int> s;
set<int> init;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 1; i <= 20; i++)
        init.insert(i);

    int n; cin >> n;
    string type;
    int x;

    for (int i = 0; i < n; i++)
    {
        cin >> type;
        if (type.compare("all") == 0)
        {
            s = init;
        }else if (type.compare("empty") == 0)
        {
            s = {};
        }else{
            cin >> x;
            if (type.compare("add") == 0)
            {
                s.insert(x);
            }
            if (type.compare("remove") == 0)
            {
                s.erase(x);
            }
            if (type.compare("check") == 0)
            {
                s.find(x)!=s.end() ? cout << "1\n" : cout << "0\n";
            }
            if (type.compare("toggle") == 0)
            {
                if(s.find(x)!=s.end()){ // 있는 경우 삭제
                    s.erase(s.find(x));
                }
                else
                { // 없는 경우 추가
                    s.insert(x);
                }
            }
        }
    }
}