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

Notice

• 다른 코딩 문제 풀이는 코딩 문제 풀이 문서 참고

문제 정보

• 문제 링크
• 난이도: Lv.3
• 문제 유형: 힙(Heap)

풀이

접근 방식

문제 설명을 읽자마자 단순 구현 문제라고 생각했고, 실제로도 우선순위 큐를 이중으로 쓰기만 하면 되는 문제다.

코드

import java.util.*;
 
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순 정렬을 위해 comparator 전달. (PriorityQueue는 기본적으로 최소 힙으로 동작하기 때문)
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        
        for(String operation : operations) {
            String[] token = operation.split(" "); // 명령어 분리
            
            if(token[0].equals("I")) {
                    maxQ.offer(Integer.valueOf(token[1]));
                    minQ.offer(Integer.valueOf(token[1]));
            } else if (token[0].equals("D")) {
                if (token[1].equals("1") && !maxQ.isEmpty()) {
                    minQ.remove(maxQ.poll());
                }
                else if (token[1].equals("-1") && !minQ.isEmpty()) {
                    maxQ.remove(minQ.poll());
                }
            }
        }
        
        if (!maxQ.isEmpty() && !minQ.isEmpty()) {
            answer[0] = maxQ.poll();
            answer[1] = minQ.poll();
        } 
        
        return answer;
    }
}

구현 중 트러블 슈팅

PriorityQueue.poll()과 ProrityQueue.peek()의 동작을 착각해서 코드를 잘못 작성해 문제가 있었다.

• PriorityQueue.poll(): 가장 우선순위가 높은 요소를 제거하고 반환한다.
• PriorityQueue.peek(): 가장 우선순위가 높은 요소를 반환한다.