DeveloperOC

🔗 문제

https://www.acmicpc.net/problem/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 연산이 주어질때마다, 결과를 출력한다.

💡 접근 방법

메모리가 작게 걸려 있기에 어떻게 풀어나가야 할지 고민을 했다.
적은 메모리를 쓰면서 시간에도 걸리지 않으려면 set 컨테이너를 사용하여 구현했다.

문제를 풀며 알게된 사실은 set과 unordered_set의 insert, erase 시간 복잡도가 다르다는 것을 알게 됐다.
set을 unordered_set으로 변경하여 문제를 진행 했다.

결과적으로는 풀게된 문제인데
다른 해답을 보니 비트마스킹을 활용해 푸는 방법이 많은 것 같다.

⚠️ 처음에 했던 실수

💻 코드

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int M;
unordered_set<int> S;
string command;
int value;
void commandStr() {
  bool isContained = S.find(value) != S.end();
  if (command == "add" && !isContained)
    S.emplace(value);
  else if (command == "remove" && isContained)
    S.erase(value);
  else if (command == "check") {
    if (isContained)
      cout << '1' << '\n';
    else
      cout << '0' << '\n';
  } else if (command == "toggle") {
    if (isContained)
      S.erase(value);
    else
      S.emplace(value);
  }
}
void commandAll() {
  S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
}
void commandEmpty() { S = {}; }

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

  for (int i = 0; i < M; ++i) {
    cin >> command;
    if (command == "all") {
      commandAll();
    } else if (command == "empty") {
      commandEmpty();
    } else {
      cin >> value;
      commandStr();
    }
  }

  return 0;
}