이중 우선순위 큐
Prob
이중 우선순위 큐 구현
I n : n push
D 1 : max pop
D -1 : min pop
Solv
max heap과 min heap으로 동시에 push 최댓값은 max heap pop, 최솟값은 min heap pop
push, pop 할 때 상대 heap에서 pop한 것 파악하기 위해 map으로 원소 카운팅
pop 했을때 map을 통해 상대 heap에서 빠진 것 존재 시 모두 pop
Check
| input | maxhq | minhq | map |
|---|---|---|---|
| I 1 | [1] | [1] | {1:1} |
| I 5 | [1, 5] | [1, 5] | {1:1, 5:1} |
| I 6 | [1, 5, 6] | [1, 5, 6] | {1:1, 5:1, 6:1} |
| D 1 | [1, 5] | [1, 5, 6] | {1:1, 5:1, 6:0} |
| D 1 | [1] | [1, 5] | {1:1, 5:0, 6:0} |
| I 7 | [1, 7] | [1, 5, 7] | {1:1, 5:0, 6:0, 7:1} |
| I 6 | [1, 6, 7] | [1, 5, 6, 7] | {1:1, 5:0, 6:1, 7:1} |
| I 8 | [1, 6, 7, 8] | [1, 5, 6, 7, 8] | {1:1, 5:0, 6:1, 7:1, 8:1} |
| D -1 | [1, 6, 7, 8] | [5, 6, 7, 8] | {1:0, 5:0, 6:1, 7:1, 8:1} |
| [1, 6, 7, 8] | [6, 7, 8] | {1:0, 5:0, 6:1, 7:1, 8:1} | |
| D -1 | [1, 6, 7, 8] | [7, 8] | {1:0, 5:0, 6:0, 7:1, 8:1} |
Ref
https://please-amend.tistory.com/entry/백준-7662번-이중-우선순위-큐-Ccpp-풀이
