Easy is Perfect

[백준] 11723번 C/C++ 풀이 _ 집합

  • melonicedlatte
  • Jul 29, 2018


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

집합

시간 제한메모리 제한제출정답맞은 사람정답 비율
1.5 초4 MB102972810192226.851%

문제

비어있는 공집합 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을 출력한다.
  • toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
  • all: S를 {1, 2, ..., 20} 으로 바꾼다.
  • empty: S를 공집합으로 바꾼다. 

입력

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

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

출력

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

예제 입력 1 

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1 

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//
//  main.cpp
//  algo
//
//  Created by 임재곤 on 2018. 7. 28..
//  Copyright © 2018년 gohn. All rights reserved.
//
 
#include <iostream>
#include <vector>
using namespace std;
#define TOTAL 20 + 1
#pragma warning(disable : 4996)
int main(int argc, const char * argv[]) {
 
    // insert code here...
    int M;
    cin >> M;
    vector<int> set_vec(TOTAL, 0);
 
    for (int m_idx = 0; m_idx < M; m_idx++) {
        char _string[5];
        int _val;
 
        scanf("%s", &_string);
        // all 이 아니면 숫자 받기 
        if (_string[1] != 'l') scanf("%d", &_val);
 
        switch (_string[0]) {
        case 'a':
            // add
            if (_string[1] == 'd') {
                set_vec.at(_val) = 1;
                break;
            }
 
            // all
            if (_string[1] == 'l') {
                for (int vec_idx = 0; vec_idx < TOTAL; vec_idx++)
                    set_vec.at(vec_idx) = 1;
                break;
            }
            break;
            // check
        case 'c':
            printf("%d\n", set_vec.at(_val));
            break;
            // remove
        case 'r':
            set_vec.at(_val) = 0;
            break;
            // toggle
        case 't':
            set_vec.at(_val) ? set_vec.at(_val) = 0 : set_vec.at(_val) = 1;
            break;
            // empty
        case 'e':
            for (int vec_idx = 0; vec_idx < TOTAL; vec_idx++)
                set_vec.at(vec_idx) = 0;
            break;
        default:
            break;
        }
 
    }
 
    return 0;
}
cs



Search