문제 11
C++ Set
처음에 빈 집합 $S$가 있다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
insert x: $S$에 정수 $x$를 추가한다.erase x: $S$에서 정수 $x$를 삭제한다.count x: $S$에 정수 $x$가 있으면1, 없으면0을 출력한다.size: $S$의 크기를 출력한다.
이미 있는 값을 추가하거나 없는 값을 삭제하면 아무 일도 일어나지 않는다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
쿼리에 포함되는 정수 $x$의 범위는 다음과 같다. $(-10^9 \le x \le 10^9)$
출력
count, size 쿼리마다 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
6 insert 1 size insert 1 size erase 1 count 1
예제 출력 1
1 1 0
공식 해설
같은 값은 하나만 저장하고 삽입·삭제·존재 확인을 처리해야 한다. $Q\le100\,000$이므로 매번 모든 원소를 찾는 대신 로그 시간 탐색을 지원하는 균형 이진 탐색 트리를 사용한다.
중복 삽입과 없는 원소의 삭제는 집합을 바꾸지 않는다.
삽입·삭제·존재 확인은 $O(\log(Q+1))$, 크기 조회는 $O(1)$이다. 전체 시간복잡도는 $O(Q\log(Q+1))$, 공간복잡도는 $O(Q)$이다.
구현 · 언어별 풀이
C++ 구현
set<int> s를 사용한다. s.insert(x)와 s.erase(x)는 중복 삽입과 없는 값의 삭제를 그대로 처리한다. 존재 여부는 s.count(x), 집합의 크기는 s.size()를 출력한다.
C 풀이
C 표준 라이브러리에는 동적 정렬 집합이 없다. 모든 질의를 먼저 읽고 등장하는 값을 정렬·중복 제거한 뒤, 각 값의 압축 인덱스에 존재 여부를 저장한다. 삽입·삭제 시 상태가 실제로 바뀔 때만 전체 크기를 갱신한다.
압축은 같은 값을 같은 위치로 대응시키므로 원소의 존재 여부와 집합 크기가 원래 집합과 같다. 각 질의는 이분 탐색 한 번으로 처리하여 전체 $O(Q \log Q)$ 시간, $O(Q)$ 공간을 사용한다.
압축 인덱스 j를 찾은 뒤 삽입은 다음처럼 처리한다. 삭제도 존재할 때만 상태와 크기를 함께 바꾼다.
// 삽입
if (!present[j]) {
present[j] = 1;
size++;
}
// 삭제
if (present[j]) {
present[j] = 0;
size--;
}Python 풀이
set의 add(), discard(), in, len()으로 처리한다. 중복 삽입은 크기를 바꾸지 않으며 discard()는 없는 원소를 지울 때도 오류를 내지 않는다.
조회에 값의 순서는 필요 없으므로 해시 집합으로 동일한 상태를 유지할 수 있다. 연산당 기대 $O(1)$, 전체 기대 $O(Q)$ 시간과 $O(Q)$ 공간이다. 이는 정렬 트리의 최악 $O(\log Q)$ 보장과는 다르다.
s = set()
s.add(x)
s.discard(x)
exists = x in s
size = len(s)Java 구현
TreeSet<Integer>의 add(), remove(), contains(), size()를 사용한다.
TreeSet<Integer> s = new TreeSet<>();
s.add(x);
s.remove(x);
boolean exists = s.contains(x);
int size = s.size();Rust 구현
BTreeSet<i32>의 insert(), remove(), contains(), len()을 사용한다. remove와 contains에는 원소의 참조를 전달한다.
use std::collections::BTreeSet;
let mut s = BTreeSet::<i32>::new();
s.insert(x);
s.remove(&x);
let exists = s.contains(&x);
let size = s.len();JavaScript 풀이
JavaScript의 Set은 중복값을 한 번만 저장한다. 이 문제는 순서나 최솟값을 요구하지 않으므로 정렬 트리 대신 add, delete, has, size로 같은 집합 상태를 유지할 수 있다. 없는 값의 delete는 집합을 바꾸지 않는다.
const s = new Set();
s.add(x);
s.delete(x);
const exists = s.has(x) ? 1 : 0;
const size = s.size;V8의 해시 집합을 사용하면 연산당 기대 $O(1)$, 전체 기대 $O(Q)$ 시간과 $O(Q)$ 공간이다. 이는 공통 풀이의 균형 트리 최악 시간 보장과 구분한다. 입력 토큰은 Number로 변환해 저장하며 문자열 "1"과 숫자 1을 섞지 않는다.