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

💡 접근 방법

문제 유형: 자료구조 / 비트마스킹 (집합 연산)

알고리즘이랄 게 없는 문제다. 시키는 대로 add / remove / check / toggle / all / empty를
구현하면 끝. 대신 제한이 이 문제의 진짜 본체다.

• 연산 횟수 M이 최대 3,000,000번
• 메모리 제한이 빡빡하게 걸려 있음
• 반면 원소 범위는 1 ~ 20으로 아주 작음

그래서 “한 번의 연산을 얼마나 싸게 처리하느냐”만 보면 된다.
메모리가 작게 걸려 있기에 어떻게 풀어나가야 할지 고민을 했고,
적은 메모리를 쓰면서 시간에도 걸리지 않으려면 set 컨테이너를 사용하여 구현했다.

문제를 풀며 알게된 사실은 set과 unordered_set의 insert, erase 시간 복잡도가 다르다는 것이다.
set은 균형 이진 탐색 트리라 연산마다 O(log n)이고,
unordered_set은 해시 테이블이라 평균 O(1)이다.
원소가 20개뿐이라 log n 차이는 사실 미미하지만, 3백만 번 반복되면 상수 차이가 체감된다.
set을 unordered_set으로 변경하여 문제를 진행 했다.

결과적으로는 풀게된 문제인데
다른 해답을 보니 비트마스킹을 활용해 푸는 방법이 많은 것 같다.
아래 다른 풀이와 비교에서 둘을 직접 비교해봤다.

⚠️ 처음에 했던 실수

처음엔 set<int>으로 짰다가 시간이 아슬아슬했다.
연산 하나하나는 O(log 20)이라 별거 아닌데, 그게 3백만 번 쌓이니까 얘기가 달라졌다.
unordered_set으로 바꾸면서 통과.

그리고 사실 더 큰 병목은 컨테이너가 아니라 입출력이었다.
연산 3백만 줄을 cin으로 읽으면 기본 설정으로는 그것만으로 시간이 날아간다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이 세 줄이 없으면 어떤 자료구조를 써도 통과하기 어렵다.
check 출력에서 endl 대신 '\n'을 쓴 것도 같은 이유다.
(endl은 매번 버퍼를 flush 한다)

💻 코드

#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();

  // 참고: unordered_set은 중복 삽입/없는 원소 삭제를 알아서 무시하므로
  //      add/remove의 isContained 검사는 없어도 결과가 같다.
  //      toggle이 이 값을 꼭 필요로 해서 한 번에 구해둔 것.
  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() {
  // 연산이 최대 3백만 개라 입출력 속도가 곧 당락이다
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> M;

  for (int i = 0; i < M; ++i) {
    cin >> command;
    // all / empty만 피연산자가 없다. 나머지는 숫자를 하나 더 읽는다
    if (command == "all") {
      commandAll();
    } else if (command == "empty") {
      commandEmpty();
    } else {
      cin >> value;
      commandStr();
    }
  }

  return 0;
}

⏱️ 시간·공간 복잡도

M = 연산 횟수(≤ 3,000,000), n = 집합 크기(≤ 20으로 상수)

이론상 O(M)이라 넉넉해 보이지만, 여기서 중요한 건 상수다.
unordered_set은 원소마다 노드를 동적 할당하고 해시를 계산하며 포인터를 따라간다.
3백만 번이면 그 상수가 그대로 실행 시간으로 나온다.

🔀 다른 풀이와 비교: unordered_set vs 비트마스킹

원소 범위가 1 ~ 20이라는 게 결정적이다.
20비트면 int 하나(32비트)에 집합 전체가 들어간다. 각 비트가 “원소가 있냐/없냐”다.

int S = 0;                              // 공집합

S |= (1 << (x - 1));                    // add x
S &= ~(1 << (x - 1));                   // remove x
cout << ((S >> (x - 1)) & 1) << '\n';   // check x
S ^= (1 << (x - 1));                    // toggle x
S = (1 << 20) - 1;                      // all
S = 0;                                  // empty

add가 이미 있는 값이어도 |=는 그대로 1이고, remove가 없는 값이어도 &= ~는 그대로 0이다.
“이미 있으면 무시”라는 조건이 연산 자체에 내장되어 있어서 존재 여부를 미리 확인할 필요가 없다.

정리하면 — 원소 범위가 작고 고정일 땐 비트마스킹이 모든 면에서 유리하다.
반대로 원소 범위가 크거나 미리 알 수 없다면 unordered_set이 맞다.
이 문제는 1 ≤ x ≤ 20이라고 대놓고 못 박아뒀으니, 출제자가 비트마스킹을 유도한 문제였던 셈이다.

컨테이너 선택에만 매달렸는데, 한 발 물러서서 제약 조건이 뭘 암시하는지 읽었어야 했다.
1 ≤ x ≤ 20 같은 작은 상한은 대체로 “비트로 접어라”는 신호다.