[JAVA] 프로그래머스 : 이중우선순위큐 (코딩테스트 고득점 kit > 힙(Heap))

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

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

min, max 우선순위 큐 두개를 이용하여 구현함

두 자료구조에 든 자료를 일치시키기 위해
minPQ에서 삭제한 값을 maxPQ에서도 삭제하고
maxPQ에서 삭제한 값을 minPQ에서 삭제하였음

** 우선순위 큐에서도 List의 remove() 함수를 사용하여 삭제가 가능하였으며 remove("값")을 넣으면 해당 값을 삭제해줌
(PriorityQueue는 Queue 인터페이스를 사용하고 Queue는 List 인터페이스를 사용하므로 List의 remove함수 사용이 가능함)

import java.util.*;
// 이중우선순위큐

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        
        Queue<Integer> minPQ = new PriorityQueue<>();
        Queue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        
        String[] operationItem;
        for(int i=0; i<operations.length; i++){
            
            //삽입일 경우
            if(operations[i].charAt(0) == 'I'){
                operationItem = operations[i].split(" ");
                
                minPQ.offer(Integer.parseInt(operationItem[1]));
                maxPQ.offer(Integer.parseInt(operationItem[1]));
            }
            //삭제일 경우
            else{
                // 빈 큐 일때 해당 연산 무시
                if(minPQ.isEmpty())
                    continue;
                
                operationItem = operations[i].split(" ");
                // 최댓값 삭제
                if(Integer.parseInt(operationItem[1]) == 1){
                    minPQ.remove(maxPQ.poll());
                }
                // 최솟값 삭제
                else{
                    maxPQ.remove(minPQ.poll());
                }
            }
        }
        
        if(!minPQ.isEmpty()){
            answer[0] = maxPQ.peek();
            answer[1] = minPQ.peek();
        }
        else{
            answer[0] = 0;
            answer[1] = 0;
        }
        
        return answer;
    }
}