제목 그대로 우선순위 큐 두 개 (minHeap, maxHeap)을 사용하여 최대값 및 최소값을 얻을 수 있다!

※ 우선순위 큐도 특정 요소를 제거할 수 있다.

즉 다음 로직을 반복하면 된다.

• 요소 추가 시, minHeap과 maxHeap에 모두 추가
• 최대값 제거 시, maxHeap에서 poll을 하고 그 요소를 minHeap에서도 제거
• 최소값 제거 시, minHeap에서 poll을 하고 그 요소를 maxHeap에서도 제거

→ 이때 추가된 요소의 개수가 제거된 요소의 개수보다 많아야 최대 최소가 존재하므로 아닌 경우에는 [0, 0]을 정답 배열로 지정해준다.

풀이 코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2]; // [최댓값, 최솟값]
        
        **PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 최소값을 위한 힙
        PriorityQueue<Integer> maxHeap 
            = new PriorityQueue<>(Collections.reverseOrder()); //최대값을 위한 힙**
        
        int count_add = 0;
        int count_delete = 0;
        
        for(int i=0; i<operations.length; i++) {
            String[] tmp = operations[i].split(" ");
            
            if(tmp[0].equals("I")) {
                minHeap.offer(Integer.parseInt(tmp[1]));
                maxHeap.offer(Integer.parseInt(tmp[1]));
                count_add++;
            }
            else if(tmp[0].equals("D")) {
                if(minHeap.size() > 0) {
                    if(tmp[1].equals("1")) {
                        // 최대값 삭제
                        int max = maxHeap.poll();
                        minHeap.remove(max);
                    }
                    else { //-1
                        // 최소값 삭제
                        int min = minHeap.poll();
                        maxHeap.remove(min);
                    }
                    count_delete++;
                }
            }
        }
        
        if(count_add - count_delete > 0) {
            answer[0] = maxHeap.poll();
            answer[1] = minHeap.poll();
        }
        
        
        return answer;
    }
}