[C++] 백준 11723 집합

 

문제

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

예제 입력 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

 

로직

---

사실 그다지 신경쓸 부분이 없어 보이는 문제이다.

문제에서 요구한 그대로 6가지의 명령에 관해 착실히 수행하는 함수를 만들어 주면 될듯 싶다.

 

라고 생각했었다.

들어올 수 있는 명령의 수는 3,000,000 이하인데 관리할 수는 20개이다.

만약 모든 명령이 all이라면 최대 연산 횟수는 60,000,000이 된다.

 

시간 제한은 1.5초로 부족할 수도 있을 연산횟수이다.

그렇다면 for문을 최대한 줄이면 어떨까 라는 생각으로 vector에서 비트 연산으로 바꿔봤지만 여전히 시간 초과가 났었다.

 

누군가 endl 때문인것 같다고 했고 endl을 '\n'로 바꾸니 통과가 됐었다.

 

그렇다면 왜 endl을 쓰면 안될까?

"Inserts a newline character into the output sequence os and flushes it as if by calling os.put(os.widen('\n')) followed by os.flush()."

C++ 공식 문서 내용 중 일부이다.

endl을 사용할 때마다 출력 시퀀스에 개행을 삽입 후 os.put(os.widen('\n')) 호출 후 os.flush()를 호출한것 처럼 flush를 하게 된다.

라는 의미다.

 

endl의 유무로 즉시 출력하냐 나중에 출력하냐로 해석할 수도 있다.

예를 들어 cout 코드 후 sleep이 오게 되었을 때 endl의 유무로 즉시 출력 또는 sleep 후 출력이 될 수 있다.

 

한마디로 endl 자체가 프로그램 성능에 엄청난 영향을 줄 수 있다는 것이다.

 

코드

---

#include <unordered_map>
#include <iostream>
#include <functional>
#include <string>

using namespace std;
int value = 0;

void Add() {
    int val;
    cin >> val;
    value |= (1 << (val - 1));
}

void Remove() {
    int val;
    cin >> val;
    value &= ~(1 << (val - 1));
}

void Check() {
    int val;
    cin >> val;
    if (value & (1 << (val - 1)))
        cout << 1 << '\n';
    else
        cout << 0 << '\n';
}

void Toggle() {
    int val;
    cin >> val;
    value ^= (1 << (val - 1));
}

void All() {
    value = 2147483647;
}

void Empty() {
    value = 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int M;
    cin >> M;
    cin.ignore();
    unordered_map<string, std::function<void()> > command;
    command["add"] = Add;
    command["remove"] = Remove;
    command["check"] = Check;
    command["toggle"] = Toggle;
    command["all"] = All;
    command["empty"] = Empty;
    
    for (int i = 0; i < M; i++) {
        string req;
        cin >> req;
        
        command[req]();
    }
    return 0;
}