[프로그래머스] 이중우선순위큐

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

이 문제는 큐에 임의의 값들을 삽입하고 임의로 삭제한 뒤 남아있는 값들 중 최댓값과 최솟값을 구하는 문제이다. 이렇게 정리하면 풀이 방법이 여러 개로 보일 수 있다. 실제로 여러 개 이기도 하고...

1. 가장 쉬운 정렬: 삽입할 때마다 정렬, 삭제 후에는 안해도 됨(n^2)
2. 힙을 두개 사용하는 방법: maxheap, minheap 이렇게 두개를 사용하면 간단하게 풀림(nlogn)

그런데 이 문제가 그렇게 좋지 않은 게 효율성 테스트 케이스가 없어서 그냥 bruteforce로 해도 풀린다. 그래서 이름은 이중우선순위큐이면서 정렬로 많이들 푸는 것 같다.

아무튼 문제의 핵심은 heap을 어떻게 활용할 것인가 이다.
일단 minheap과 maxheap이 각각 필요하고 두 힙에 대해 삽입과 삭제를 수행할 거다. 삭제할 때는 PriorityQueue 자료형이기 때문에 Queue의 remove(value)를 이용할 수 있다. 따라서 maxheap은 minheap의 값을 이용해 삭제를 수행할 수 있고 minheap은 maxheap의 값을 이용해 삭제를 수행할 수 있게 된다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minPQ = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        for(String op : operations){
            String[] splitOps = op.split(" ");
            String opCode = splitOps[0];
            String opNum = splitOps[1];
            if(opCode.equals("I")){
                minPQ.add(Integer.parseInt(opNum));
                maxPQ.add(Integer.parseInt(opNum));
            }
            else if(opCode.equals("D")){
                if(opNum.equals("-1")){
                    maxPQ.remove(minPQ.poll());
                }
                else if(opNum.equals("1")){
                    minPQ.remove(maxPQ.poll());
                }
            }
        }
        int[] result = {0, 0};
        if(minPQ.size() > 0 && maxPQ.size() > 0){
            result[0] = maxPQ.peek();
            result[1] = minPQ.peek();
        }
        return result;
    }
}