문제 설명

문제 바로가기
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어		|수신 	탑(높이) <-- 오타인듯?
I 숫자		|큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 	|최댓값을 삭제합니다.
D -1		|큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

---

생각해보기

max heap과 min heap 각각을 써야 할 것 같다.

삽입 명령에 대해서는 모든 힙에 삽입하면 될 것이다.
삭제 명령에 대해서는 최댓값이면 max heap에서, 최솟값이면 min heap에서 삭제해야 한다.

그런데 하나의 heap에서만 삭제하면 두 힙이 일치하지 않게 된다.
예를 들어 최댓값 삭제 명령이 여러번 실행되어 max heap이 텅 비게 되더라도 min heap에는 값이 들어있게 된다. 그러면 마지막에 최댓값, 최솟값 배열을 반환할 때 문제가 된다.

따라서, 이중우선순위큐라는 가상의 큐의 size를 기록하기로 한다.
그리고 각 heap은 특정 시점에 size를 벗어나는 값들을 버리도록 한다. 이 작업을 fixHeap이라고 한다.
다만 모든 삭제 연산에 대해서 fixHeap하면 삭제 연산의 비용이 너무 켜져버릴 것이다.

fixHeap의 시점을 최대한 미룬다.
두 힙의 불일치는 새로운 값을 삽입할 때 비로소 문제를 발생시킨다.
따라서 삽입 연산 시 삽입 전에 두 힙을 fixHeap한다.

---

풀이

package _0325.이중우선순위큐;

import java.util.*;
class Solution {
    int size = 0;
    Queue<Integer> minHeap = new PriorityQueue<>();
    Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

    public int[] solution(String[] operations) {
        for(String op : operations) {
            StringTokenizer st = new StringTokenizer(op);
            if(st.nextToken().equals("I")) {
                operateI(st.nextToken());
            } else {
                operateD(st.nextToken());
            }
        }
        fixHeaps(); // <-- 이건 없어도 되겠다.
        return size < 1 ?
                new int[]{0, 0} : new int[]{maxHeap.peek(), minHeap.peek()};
    }

    private void operateD(String param) {
        if(size < 1) return;
        if(param.charAt(0) == '-') {
            minHeap.poll();
        } else {
            maxHeap.poll();
        }
        size--;
    }

    private void operateI(String param) {
        int value = Integer.parseInt(param);
        fixHeaps();
        minHeap.offer(value);
        maxHeap.offer(value);
        size++;
    }

    private void fixHeaps() {
        if(maxHeap.size() != size) fixHeap(maxHeap);
        if(minHeap.size() != size) fixHeap(minHeap);
    }
    private void fixHeap(Queue<Integer> q) {
        int[] temp = new int[size];
        for(int i = 0; i < size; i++) temp[i] = q.poll();
        q.clear();
        for(int i = 0; i < size; i++) q.offer(temp[i]);
    }
}

수정1

위 풀이를 올리고 나니 fixHeap에서 배열을 쓰지 않고도 할 수 있을 것 같다.
대신, 새로운 우선순위큐를 생성해서 기존 큐(포인터)를 바꾸면 될 것이다.
데이터가 충분히 크다면 메모리 사용량을 줄일 수 있을 것이다.
fixHeap을 다음과 같이 바꾸어 보았다.

    private void fixHeaps() {
        if(maxHeap.size() != size) fixMaxHeap();
        if(minHeap.size() != size) fixMinHeap();
    }

    private void fixMinHeap() {
        Queue<Integer> newQ = new PriorityQueue<>();
        for(int i = 0; i < size; i++) newQ.offer(minHeap.poll());
        minHeap = newQ;
    }
    
    private void fixMaxHeap() {
        Queue<Integer> newQ = new PriorityQueue<>(Comparator.reverseOrder());
        for(int i = 0; i < size; i++) newQ.offer(maxHeap.poll());
        maxHeap = newQ;
    }

Java에선 포인터의 포인터(다중 포인터)를 쓸 수 없다보니 코드가 늘어나버렸다.

테스트케이스가 빈약하다보니 큰 차이는 보이지 않는다.

---

그런데

다른 사람의 풀이를 보다 보니 "이게 돼?"하는 코드들이 있었다.
테스트 케이스가 많이 빈약한 거 같다.
내 풀이도 틀렸을지도 모르겠다.