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

문제 설명

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

문제 풀이

• 우선 순위큐 2개를 이용하여 풀이하였다.
• max heap 역할을 하는 큐를 하나 생성한다.
• 각 명령어에 대한 로직인 다음과 같다.

  • Insert일 경우 : 큐에 추가해줌
  • 최대값 삭제일 경우 : 큐에서 poll() 해줌
  • 최소값 삭제일 경우
    - min heap 역할을 하는 큐를 생성
    - min heap에 max heap 원소 모두 더해줌
    - min heap에서 poll() 해줌
    - max heap 초기화 후에 min heap 원소 모두 더해줌

소스 코드 (JAVA)

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        for (int i = 0; i < operations.length; i++) {
            StringTokenizer st = new StringTokenizer(operations[i], " ");
            if (st.nextToken().charAt(0) == 'I') {
                maxQ.add(Integer.parseInt(st.nextToken()));
            } else {
                if (maxQ.isEmpty())
                    continue;
                //최대값 빼줌
                if (st.nextToken().charAt(0) == '1')
                    maxQ.poll();
                //최소값 빼줌
                else {
                    minQ.addAll(maxQ);
                    minQ.poll();
                    maxQ.clear();
                    maxQ.addAll(minQ);
                    minQ.clear();
                }
            }
        }
        minQ.addAll(maxQ);
        if (maxQ.isEmpty()) return new int[] {0, 0};
        else return new int[] {maxQ.poll(), minQ.poll()};
    }
}