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

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

프로그래머스

🤔 문제분석

최대 힙큐와 최소힙큐를 두어서 최대값과 최소값을 POP 할때마다 자료를 옮긴뒤 POP 해주면 된다.

1. 배열에 집어 넣을때에는 최소 힙큐에 집어넣는다.
2. 최대값을 꺼낼때에는 최소 힙큐에 모든 값을 최대 힙큐에 넣어준다. 그리고 최대 힙큐를 POP 한다.
3. 최소값을 꺼낼때에는 최대 힙큐에서 모든 값을 최소 힙큐에 넣어준다. 그리고 최소 힙큐를 POP 한다.

💻 코드

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public static class Number {
        int index;
        int number;
        Number(int number, int index)
        {
            this.number = number;
            this.index = index;
        }

    }

    public int[] solution(String[] operations) {
        int n = operations.length;

        DualPriorityQueue queue = new DualPriorityQueue();

        for(String operation : operations)
        {
            String[] temp = operation.split(" ");
            if(temp[0].equals("I")) {
                queue.push(Integer.parseInt(temp[1]));
            } else {
                if(Integer.parseInt(temp[1]) == 1) {
                    // 최대값 POP
                    queue.popMax();

                } else {
                    // 최소값 POP
                    queue.popMin();
                }
            }
        }
        int[] answer = new int[2];
        answer[0] = queue.getMax();
        answer[1] = queue.getMin();
        return answer;
    }

    public static class DualPriorityQueue
    {
        private final PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        private final PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());

        public void push(int number)
        {
            if(maxQueue.isEmpty())  {
                minQueue.add(number);
            }
            else {
                if(maxQueue.peek() > number) {
                    minQueue.add(number);
                } else {
                    maxQueue.add(number);
                }
            }
        }

        public int getMax()
        {
            while(!minQueue.isEmpty())
            {
                maxQueue.add(minQueue.poll());
            }

            if(!maxQueue.isEmpty())  {
                return maxQueue.peek();
            }
            else {
                return 0;
            }
        }

        public int getMin()
        {
            while(!maxQueue.isEmpty())
            {
                minQueue.add(maxQueue.poll());
            }

            if(!minQueue.isEmpty()) {
                return minQueue.peek();
            }
            else {
                return 0;
            }
        }

        public int popMax()
        {
            while(!minQueue.isEmpty())
            {
                maxQueue.add(minQueue.poll());
            }

            if(!maxQueue.isEmpty())  {
                return maxQueue.poll();
            }
            else {
                return 0;
            }
        }

        public int popMin()
        {
            while(!maxQueue.isEmpty())
            {
                minQueue.add(maxQueue.poll());
            }

            if(!minQueue.isEmpty()) {
                return minQueue.poll();
            }
            else {
                return 0;
            }
        }
    }
}