문제 12
C++ Map
처음에 빈 맵 $M$이 있다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
insert k v: $M$에 키 $k$와 값 $v$를 저장한다.erase k: $M$에서 키 $k$를 삭제한다.count k: $M$에 키 $k$가 있으면1, 없으면0을 출력한다.get k: $M$에 키 $k$가 있으면 대응하는 값을, 없으면-1을 출력한다.size: $M$에 저장된 키의 개수를 출력한다.
이미 있는 키를 추가하면 값을 새로 주어진 값으로 바꾸고, 없는 키를 삭제하면 아무 일도 일어나지 않는다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
쿼리에 포함되는 정수 $k$, $v$의 범위는 다음과 같다. $(-10^9 \le k, v \le 10^9)$
출력
count, get, size 쿼리마다 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
13 size insert 3 10 get 3 count 3 insert 3 20 get 3 size insert 5 -7 size erase 3 count 3 get 3 get 5
예제 출력 1
0 10 1 20 1 2 0 -1 -7
공식 해설
키 하나에는 값 하나만 대응하므로, 키를 기준으로 탐색하는 맵을 사용한다. 키의 추가·삭제·탐색을 로그 시간에 처리하면 $Q\le100\,000$에서 충분하다.
이미 있는 키를 삽입하면 대응하는 값만 바꾸고, 없는 키라면 새로 추가한다. 삭제는 키가 있을 때만 수행한다.
조회는 저장 상태를 바꾸지 않는다. 값 자체가 $-1$일 수도 있으므로 없는 키와 값이 $-1$인 키를 구분해야 한다. 전체 시간복잡도는 $O(Q\log(Q+1))$, 공간복잡도는 $O(Q)$이다.
구현 · 언어별 풀이
C++ 구현
map<int, int> m을 사용한다. 삽입·덮어쓰기는 m[k] = v, 삭제는 m.erase(k)로 처리한다. m.count(k)는 존재 여부, m.size()는 키의 개수이다.
값 조회에는 auto it = m.find(k)를 사용하고, it == m.end()이면 $-1$, 아니라면 it->second를 출력한다. 조회에서 m[k]를 사용하면 없는 키가 새로 추가되므로 사용하지 않는다.
C 풀이
모든 질의를 저장하고 등장하는 키를 정렬·압축한다. 압축 인덱스별로 값 배열과 존재 배열을 따로 둔다. 값이 $-1$일 수도 있으므로 값 자체를 부재 표시로 쓰지 않는다.
키의 동일성은 압축 뒤에도 유지되고, 대입은 값만 교체하며 최초 삽입·실제 삭제만 크기를 바꾼다. 키를 이분 탐색하면 전체 $O(Q \log Q)$ 시간과 $O(Q)$ 공간으로 모든 질의를 처리한다.
압축 인덱스 j의 최초 대입에서만 크기를 늘리고, 기존 키에는 값을 덮어쓴다.
if (!present[j]) {
present[j] = 1;
size++;
}
values[j] = value;
int result = present[j] ? values[j] : -1;Python 풀이
dict에 키와 값을 저장하고 get(key, -1), key in d, len(d)를 사용한다. 없는 키의 조회는 삽입하지 않으며 삭제에는 pop(key, None)을 쓸 수 있다.
필요한 것은 키의 동일성뿐이므로 해시 맵으로 같은 대입·삭제·조회 결과를 얻는다. 전체 기대 $O(Q)$ 시간, $O(Q)$ 공간이며 키 정렬 순서를 유지하는 방법은 아니다.
조회는 get, 존재 검사는 in으로 구분한다.
d = {}
d[key] = value
exists = key in d
result = d.get(key, -1)
d.pop(key, None)Java 구현
TreeMap<Integer, Integer>에 put(), remove(), containsKey(), getOrDefault(key, -1)을 사용한다. $-1$이 저장된 키도 존재할 수 있으므로 count에는 containsKey()를 쓴다.
TreeMap<Integer, Integer> d = new TreeMap<>();
d.put(key, value);
boolean exists = d.containsKey(key);
int result = d.getOrDefault(key, -1);
d.remove(key);Rust 구현
BTreeMap<i32, i32>의 insert(), remove(), get(), contains_key()를 사용한다. 조회 결과는 get(&key).copied().unwrap_or(-1)로 얻을 수 있다. 이 조회는 맵에 키를 추가하지 않는다.
use std::collections::BTreeMap;
let mut d = BTreeMap::<i32, i32>::new();
d.insert(key, value);
let exists = d.contains_key(&key);
let result = d.get(&key).copied().unwrap_or(-1);
d.remove(&key);JavaScript 풀이
Map의 set(k, v)는 기존 키의 값을 덮어쓰고 delete(k)는 없는 키도 그대로 처리한다. 존재 여부는 has(k), 키 수는 size이다. 키와 값은 $\pm10^9$이므로 Number로 저장한다.
const m = new Map();
m.set(k, v);
const exists = m.has(k) ? 1 : 0;
const value = m.has(k) ? m.get(k) : -1;
m.delete(k);m.get(k) || -1은 저장한 값이 $0$일 때도 $-1$을 반환하므로 잘못이다. 키 순서가 필요 없으므로 V8 해시 맵으로 전체 기대 $O(Q)$ 시간, $O(Q)$ 공간에 처리하며 균형 트리의 최악 시간 보장과는 다르다.