[프로그래머스][JAVA][Lv. 3] 이중우선순위큐

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42628

---

제한 사항

---

입출력 예

---

풀이

import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((i, j) -> j - i);
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        int[] answer = {};
        
        for (int i = 0; i < operations.length; i++) {
            if (operations[i].charAt(0) == 'I') {  // 추가
                int num;
                
                if (operations[i].charAt(2) == '-') {  // 음수
                    num = Integer.parseInt(operations[i].substring(3, operations[i].length())) * -1;
                }
                else {  // 양수
                    num = Integer.parseInt(operations[i].substring(2, operations[i].length()));
                }
                maxQueue.add(num);
                minQueue.add(num);
            }
            else {  // 삭제
                int num;
                
                if (operations[i].contains("-")) {  // 최솟값 삭제
                    if (minQueue.size() != 0) {
                        num = minQueue.poll();
                        maxQueue.remove(num);
                    }
                }
                else {  // 최댓값 삭제
                    if (maxQueue.size() != 0) {
                        num = maxQueue.poll();
                        minQueue.remove(num);
                    }
                }
            }
        }
        return minQueue.size() == 0 ? new int[] { 0, 0} : new int[] { maxQueue.poll(), minQueue.poll() };
    }
}

---

후기

아마 대부분 PriorityQueue를 이용해서 풀었을 것이라 생각한다. Deque 인터페이스가 있던데 이걸 사용해볼걸 그랬다... 그냥 Queue 인터페이스를 LinkedList를 이용해서 사용하는 것처럼 다형성을 이용해 Deque도 LinkedList 등의 클래스를 이용할 수 있다.

Deque 구현체들

그런데 위 문제는 크기에 따라 먼저 나오는 것을 미리 정해놔야 하므로 Deque를 사용한다고 해도 정렬을 따로 하지 않는 이상 좋은 방법으로는 구현하기가 힘들 것 같다. 그렇기 때문에 PriorityQueue를 이용해서 Deque처럼 구현하는 편이 더 낫다고 생각된다. 그리고 나는 remove() 메서드를 사용했지만 최소, 최대 힙을 이용해서 모든 값을 서로 이동시키면서 처리하는 것이 나을 수도 있겠다.