백준 7662. 이중 우선순위 큐

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

금방 풀줄 알았는데 처음에 길을 잘못들어 꽤 애먹었다.

처음에 한 생각은 우선순위 큐를 minHeap, maxHeap 두개 만들어서 D 1 이면 maxHeap에서 pop 해주고 D -1 이면 minHeap 에서 빼주면 될것 같았는데 이것만으로는 부족했다. 

 

왜냐하면 이렇게 했을 경우에 한쪽 우선순위 큐에서 이미 pop 해서 없어진 숫자가 다른 쪽에는 남아 있을수도 있기 때문이다.

어처피 최소 최대 값만 출력하면 되서 상관없을 것 같았는데 아니었다.

 

위 문제의 해결 방법은 hashmap을 써서 해결하면 된다.

I num 연산을 할때마다 map[num]++ 을 해주고, 

D 연산을 할때 map[top] 이 0이면 이미 큐에 존재하지 않는 숫자이므로 그냥 pop 해주고 map[top] > 0 이상이면 지워주면 된다.