이중우선순위큐

문제

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

코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};

        PriorityQueue<Integer> rpq = new PriorityQueue<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for(String oper : operations){
            String[] oper_arr = oper.split(" ");

            String cmd = oper_arr[0];
            int arg = Integer.valueOf(oper_arr[1]);

            if(oper_arr[0].equals("I")){
                pq.add(arg);
                rpq.add(arg);
            }else{
                if(pq.isEmpty() || rpq.isEmpty())
                    continue;
                else if(pq.peek() == rpq.peek()){
                    pq.poll();
                    rpq.poll();

                    if(pq.isEmpty() || rpq.isEmpty()){
                        while(!pq.isEmpty())
                            pq.poll();
                        while(!rpq.isEmpty())
                            rpq.poll();
                    }

                }else if(arg == 1)
                    pq.poll();
                else
                    rpq.poll();

                if(!pq.isEmpty() && !rpq.isEmpty() && pq.peek() < rpq.peek()){
                    while(!pq.isEmpty())
                        pq.poll();
                    while(!rpq.isEmpty())
                        rpq.poll();
                }

            }


        }

        if(!pq.isEmpty() && !rpq.isEmpty()){
            answer[0] = pq.peek();
            answer[1] = rpq.peek();
        }


        return answer;
    }
}

피드백

• 단 하나의 테케를 못넘어 갔는데, 그것은 min heap과 max heap이 서로의 영역을 넘어갈 때 이다.
  • 즉 min_heap.peek() > max_heap.peek() 일 때 처리를 안해주었다.
• 서로가 역전되는 상황을 생각할 필요가 있다.