[프로그래머스] 힙(Heap) - 이중우선순위큐 (JAVA)

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

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어
I 숫자 : 큐에 주어진 숫자를 삽입합니다.
D 1: 큐에서 최댓값을 삭제합니다.
D -1: 큐에서 최솟값을 삭제합니다.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
• 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
  
  

풀이방향

문제 이름에 풀이방향이 주어진 케이스이다.
최댓값/최솟값을 보면 우선순위큐를 사용해야겠다는게 감이와야 한다.
그리고 제목에서 우선순위큐를 두 개 이용해서 풀라고 힌트를 준다.

간단하게 최대 힙(Max Heap), 최소 힙(Min Heap)을 이용하면 된다.
각각의 큐를 두 개 만들고 명령어 문자열을 잘라서 명령어에 따라 큐에 삽입/삭제 연산을 하면 된다.
삽입 연산 시 2개의 큐에 값을 삽입하고 삭제 연산 시 최댓값이면 최대 힙에서 첫번째 값 반환 후 삭제, 최소 힙에서 최댓값 반환 받은 값 삭제, 최솟값일 시에는 반대로 삭제 연산을 수행하면 된다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i =0; i<operations.length; i++){
            
            if(operations[i].substring(0,1).equals("I")){
                pq1.offer(Integer.parseInt(operations[i].substring(2)));
                pq2.offer(Integer.parseInt(operations[i].substring(2)));
                continue;
            }
            
            if(pq1.isEmpty()) continue;
            
            switch(operations[i].substring(2)){
                case "1":
                    int max = pq2.poll();
                    pq1.remove(max);
                    break;
                case "-1":
                    int min = pq1.poll();
                    pq2.remove(min);
                    break;
            }
            
        }
        
        if(pq1.size() > 0 ) {
            answer[0] = pq2.peek();
            answer[1] = pq1.peek();
        }
        
        return answer;
    }
}