[BOJ] 백준 11723번 집합 풀이

| |
백준 온라인 저지 백준 11723번 - 집합 C++ 풀이


문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

  • add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
  • remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
  • check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
  • toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
  • all: S를 {1, 2, …, 20} 으로 바꾼다.
  • empty: S를 공집합으로 바꾼다.


입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.


출력

check 연산이 주어질때마다, 결과를 출력한다.


풀이

집합 자료구조를 사용한 시뮬레이션 문제이지만 맞게 풀었음에도 불구하고 입출력 내용이 많아서 시간 초과가 발생한다. 또 이 문제는 집합 자료구조 사용없이 숫자의 범위가 0 ~ 20으로 작다는 점을 이용해 비트마스킹 기법을 이용하여 더 빠르게 풀 수도 있는데 이 방법 또한 입출력 때문에 시간 초과가 발생한다. 이 문제를 풀다가 구글링을 통해 여기까지 왔다는 것은 아마 문제를 못 풀어서가 아니라 원인 모를 시간 초과 에 막혔기 때문일 것이다. 따라서 C++의 경우만 적자면 아래와 같이 표준 입출력 스트림의 설정을 건드는 코드를 앞부분에 추가해줘야 한다.

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

채점 기준이 사실 좀 이상한 문제이다. 비트마스킹을 사용하지 않을 경우 시간 초과가 나는 문제도 아니고… 거의 사용하는 언어의 빠른 입출력 방법을 아는지 묻는 문제에 가까운 것 같다. 풀이 코드는 집합을 사용한 경우와 비트마스킹을 사용한 경우 두가지를 모두 첨부한다.


전체 코드

  • 집합 자료구조 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <set>
using namespace std;

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

    set<int> s;
    int M; cin>>M;

    while(M--){
        int x;
        string str; cin>>str;
        if(str=="add"){
            cin>>x;
            s.insert(x);
        }
        else if(str=="remove"){
            cin>>x;
            s.erase(x);
        }
        else if(str=="check"){
            cin>>x;
            cout<<(s.find(x)!=s.end())<<'\n';
        }
        else if(str=="toggle"){
            cin>>x;
            if(s.find(x)==s.end()) s.insert(x);
            else s.erase(x);
        }
        else if(str=="all"){
            for(int i=1;i<=20;i++) s.insert(i);
        }
        else s.clear();
    }

    return 0;
}


  • 비트마스킹 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>
using namespace std;

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

    int S=0;
    int M; cin>>M;

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

    return 0;
}
0%