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

문제 : programmers.co.kr/learn/courses/30/lessons/42628

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

두 개의 Priority Queue를 사용하여 하나는 오름차순으로, 다른 하나는 내림차순으로 정렬하여 구현한다.

 

이 때, 별도로 원소의 갯수를 counting 하는 size 변수를 두어 size가 0이 되면 두 queue를 모두 clear 해 주어야 한다.

만일 이 과정을 넣어주지 않으면 다음과 같은 문제가 발생할 수 있다.

 

• 가정 : 이중 우선순위 큐 (이하 dpq)는 1, 2, 3을 원소로 가지고 있다.
• 전개
  • 최솟값을 두 번 poll 한다. = 오름차순으로 정렬된 priority queue (이하 minQueue)에서 두 번 poll 한다. 
  • 최댓값을 한 번 poll 한다. = 내림차순으로 정렬된 priority queue (이하 maxQueue)에서 한 번 poll 한다.
    • 현재 상태 - minQueue: [3], maxQueue: [2, 1]
  • dpq에 4를 추가한다.
    • 현재 상태 - minQueue: [3, 4], maxQueue: [4, 2, 1]
• 결과
  • dqp에서 최솟값을 poll 하면 3이 출력되는 오류 발생

소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
        int size = 0;

        for (String operation : operations) {
            String[] op = operation.split(" ");
            String instruction = op[0];
            int value = Integer.parseInt(op[1]);

            if (instruction.equals("I")) {
                minQueue.offer(value);
                maxQueue.offer(value);
                size++;
            } else {
                if (value == 1) {
                    // remove maximum
                    if (maxQueue.isEmpty()) {
                        continue;
                    }
                    maxQueue.poll();
                } else {
                    // remove minimum
                    if (minQueue.isEmpty()) {
                        continue;
                    }
                    minQueue.poll();
                }
                size--;
                if (size == 0) {
                    //minQueue.clear();
                    //maxQueue.clear();
                }
            }
        }

        if (size == 0) {
            return new int[] {0, 0};
        }
        return new int[] {maxQueue.poll(), minQueue.poll()};
    }
}