[Heap] 이중 우선순위 큐 - Java코드

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

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

 

문제

 

이해

우선순위큐를 최소값 정렬과 최댓값 정렬로 2개를 만들면 쉽게 풀 수 있다.

 

풀이

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Solution {
    public static int[] solution(String[] operations) {
        int[] answer = new int[2];
        //최소 힙, 최대 힙
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());

        for (String op : operations) {
            StringTokenizer st = new StringTokenizer(op);
            String judge = st.nextToken();
            int value = Integer.parseInt(st.nextToken());
            switch (judge) {
                case "I":
                    pq.offer(value);
                    maxPq.offer(value);
                    break;
                case "D":
                    if(pq.size()<1)
                        break;
                    if(value > 0){
                        int max = maxPq.poll();
                        pq.remove(max);
                    }else{
                        int min = pq.poll();
                        maxPq.remove(min);
                    }
                    break;
            }
        }
        if(pq.size() > 0 ) {
            answer[0] = maxPq.poll();
            answer[1] = pq.poll();
        }
        return answer;
    }
}