D. 이중 우선순위 큐

ProblemD_Kor.pdf

두 개의 Priority Queue(heap) 를 이용해서 문제를 해결할 수 있다.

하나는 max heap이고 하나는 min heap 이다.

heap에 원소의 값과 동시에 index도 같이 pair로 삽입한다.

그리고 pop 될 때 해당 index에 visit 체크를 해주고, 최대 최소 값을 구할 때에 이미 visit가 체크된 것은 무시해주면 된다.

이러한 테크닉은 코딩이 편하며, 시간복잡도에 영향이 없다.

하지만, 공간 복잡도에는 영향이 있지만 빅오표기법 상으로는 영향이 없다.

(Memory sensitive 한 문제에서는 직접 heap를 구현해야할 수도 있다.)

처음에 문제를 각 쿼리마다 최대, 최소 값을 출력해야 되는 문제를 오해하고 생각해 보다 간단한 방법이 존재할 수도 있다.

** 대회 때는 없던 크리티컬한 데이터가 안나와 수정해 올립니다. (10/2 17:10)

D.cpp