[ps] 이중우선순위큐

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

문제 설명

이중 우선순위 큐는 최댓값과 최솟값 연산을 할 수 있는 자료구조를 말한다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 구현한다. 단, 최댓값 또는 최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우 하나만 삭제한다.

이중 우선순위 큐가 수행하는 연산은 다음과 같다.

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

문제의 조건은 다음과 같다.

• 수행할 연산의 횟수는 1 이상 1000000 이하이다.
• 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제한다.
• 빈 큐에 데이터를 삭제하는 연산은 무시한다.

문제 풀이

우선순위 큐 자료구조 사용

import java.util.*;

public class Main {

    public static class DoublePriorityQueue {

        private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        public void push(int data) {
            minHeap.offer(data);
        }

        public boolean isEmpty() {
            return minHeap.isEmpty() && maxHeap.isEmpty();
        }

        public Integer getMax() {
            if (isEmpty()) {
                return 0;
            }
            while (!minHeap.isEmpty()) {
                maxHeap.add(minHeap.poll());
            }
            return maxHeap.peek();
        }

        public Integer getMin() {
            if (isEmpty()) {
                return 0;
            }
            while (!maxHeap.isEmpty()) {
                minHeap.add(maxHeap.poll());
            }
            return minHeap.peek();
        }

        public void removeMin() {
            while (!maxHeap.isEmpty()) {
                minHeap.add(maxHeap.poll());
            }
            minHeap.poll();
        }

        public void removeMax() {
            while (!minHeap.isEmpty()) {
                maxHeap.add(minHeap.poll());
            }
            maxHeap.poll();
        }

    }

    public static class Solution {

        public int[] solution(String[] operations) {
            DoublePriorityQueue doublePriorityQueue = new DoublePriorityQueue();

            for (String operation : operations) {
                String[] split = operation.split(" ");
                int number = Integer.parseInt(split[1]);

                if ("I".equals(split[0])) {
                    doublePriorityQueue.push(number);
                } else if (number == 1) {
                    doublePriorityQueue.removeMax();
                } else if (number == -1) {
                    doublePriorityQueue.removeMin();
                }
            }

            int[] answer = new int[2];
            answer[0] = doublePriorityQueue.getMax();
            answer[1] = doublePriorityQueue.getMin();

            return answer;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new String[]{"I 7","I 5","I -5","D -1"});
    }

}

이중 우선순위 큐를 사용하는 경우, 삽입 연산의 시간 복잡도는 O(log${_2}^{N}$)이다. 최댓값/최솟값을 삭제하거나 조회하는 연산을 연속적으로 동일한 연산을 수행하는 경우, 데이터를 다른 우선순위 큐로 옮길 필요가 없으므로, 시간 복잡도는 O(1)이다. 하지만 같은 우선순위 큐에서 연산을 수행하더라도 현재 데이터를 가지고 있는 큐가 삽입 연산을 수행하는 큐가 아니면서 큐에 삽입된 데이터가 쌓인 경우는 예외이다. 마찬가지로 매번 다른 연산을 번갈아가면서 수행하는 경우, 데이터를 다른 우선순위 큐로 옮겨야 하므로 시간 복잡도는 O(N log${_2}^{N}$)이다.

덱 자료구조 사용

import java.util.*;

public class Main {

    public static class Solution {

        public int[] solution(String[] operations) {
            LinkedList<Integer> deQueue = new LinkedList<>();

            for (String operation : operations) {
                String[] split = operation.split(" ");
                int number = Integer.parseInt(split[1]);
                if ("I".equals(split[0])) {
                    deQueue.offer(number);
                    deQueue.sort(null);
                } else if (number == 1) {
                    deQueue.pollLast();
                } else if (number == -1) {
                    deQueue.pollFirst();
                }

            }

            boolean isEmpty = deQueue.isEmpty();
            int[] answer = new int[2];
            answer[0] = isEmpty ? 0 : deQueue.peekLast();
            answer[1] = isEmpty ? 0 : deQueue.peekFirst();

            return answer;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new String[]{"I 7","I 5","I -5","D -1"});
    }

}

반면, 덱 자료구조를 사용하는 경우, 삽입 연산을 수행할 때마다 정렬을 수행한다. 자바의 기본 정렬 알고리즘은 데이터의 길이에 따라 binary insertion sort 또는 tim sort를 사용하기 때문에 이미 정렬된 상태에서 정렬을 수행하게 된다면 시간 복잡도는 O(N)이다. 최댓값/최솟값을 삭제하는 연산의 시간 복잡도는 O(1)이다.

비교	이중 우선순위 큐	덱
삽입	O(log${_2}^{N}$)	O(N)
삭제 및 조회	O(N log${_2}^{N}$)	O(1)

삽입 연산이 많고, 최댓값/최솟값 연산을 번갈아가면서 수행하는 경우가 적다면 이중 우선순위 큐를 사용해도 괜찮을 것 같다. 하지만 이 문제에서는 예측할 수 없기 때문에 덱을 사용하는 것이 더 좋은 상황이 많을 것 같다.