[코딩테스트 연습] 이중우선순위큐

 

문제: https://programmers.co.kr/learn/courses/30/lessons/42628

---

쿼리의 개수가 100만입니다.

하나의 쿼리를 로그 시간에 처리해야함을 알 수 있습니다.

N개의 숫자에 대한 최소/최대를 O(logN)에 구하려면 힙을 사용해야 합니다.

 

다만, O(logN)만에 최소/최대를 모두 다 구해야하니 최소힙, 최대힙 이렇게 두 개를 선언해줍니다.

 

여기에 모두 숫자를 넣게되면 한 번 넣을 때 마다 두 번씩 넣는 꼴이 되니,

최소힙, 최대힙에 숫자를 넣는 것과는 별개로

정수 두 개 front, rear를 사용해서 실제로 입력받은 수를 세줍니다.

0. 초기화는 front = rear = 0

1. 숫자가 들어오면 rear++

2. 숫자를 제거하면 front++

3. 힙이 비었는지 체크는 front == rear 이면 힙이 빈 것입니다.

 

또 한 가지 중요한 조건이 있습니다.

front, rear만으로도 큐가 빈 것처럼 흉내낼 수는 있지만

실제로 front == rear 시점이 되면 큐를 비워줘야 합니다.

if (f == r) {
    while (!minHeap.empty()) minHeap.pop();
    while (!maxeap.empty()) maxHeap.pop();
}

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42628.cc