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

전에 백준에서 비슷한 문제를 풀어본 기억이 있어서 쉽게 해결했다.

힙을 이용해서 직접 구현해야 한다면 꽤 복잡해질 것 같은데 Java에는 우선순위 큐가 정의되어있기 때문에 

그냥 두 개의 우선순위 큐를 만들어서 풀었다.

---

로직

낮은 숫자부터 정렬되는 우선순위 큐와 높은 숫자부터 정렬되는 우선순위 큐를 선언한다.

operations 배열을 순회하며 명령어와 숫자를 분리하고 명령어가 삽입인 경우 두 큐 모두에 추가하고

명령어가 삭제라면 먼저 queue가 비어있는지 확인하고 비어있지 않으면 최솟값 삭제인지 최댓값 삭제인지 구별한다.

최솟값 삭제라면 queue1의 값을 peek 해서 저장하고 queue1에서 하나를 삭제한다. 그리고 peek 했던 값을 queue2에서 삭제한다. 최댓값 삭제라면 반대로 진행하면 된다.

최종적으로 큐가 비어있지 않으면 각 큐에서 값을 빼서 answer 배열에 복사하고 큐가 비어있으면 0,0을 반환한다.

---

최종 코드

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};

        // 낮은 숫자 우선순위 큐
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        // 높은 숫자 우선순위 큐
        PriorityQueue<Integer> queue2 = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < operations.length; i++) {
            String[] temp = operations[i].split(" ");
            String commend = temp[0];
            int num = Integer.parseInt(temp[1]);

            // 명령어가 삽입인 경우
            if (commend.equals("I")) {
                queue1.add(num);
                queue2.add(num);
                // 명령어가 삭제인 경우
            } else {
                // queue가 비어있지 않으면
                if (!queue1.isEmpty()) {
                    // 최솟값 삭제인 경우
                    if (num == -1) {
                        int t = queue1.peek();
                        queue1.remove();
                        queue2.remove(t);
                        // 최댓값 삭제인 경우
                    } else {
                        int t = queue2.peek();
                        queue2.remove();
                        queue1.remove(t);
                    }
                }
            }
        }

        // queue가 비어있지 않으면
        if (!queue1.isEmpty()) {
            answer[0] = queue2.poll();
            answer[1] = queue1.poll();
        }
        return answer;
    }
}