[JAVA] 힙 : 이중 우선순위 큐

1. 문제내용

요약
I 숫자는 큐에 삽입
D 1은 최대값 삭제
D -1은 최솟값 삭제
위 세가지를 진행하고 원하는 데로 진행하고 큐에 남은 값이 있을 때 {최대값, 최소값} 을 출력하라

2. 접근방법
최대, 최소값을 찾는 방법에 힙을 사용하면 간편하게 된다는 걸 생각해 우선순위 큐를 사용해 적용해보면 될 것 같다

3. 구현과정

최대, 최소값을 관리할 큐 두개 생성

PriorityQueue<Integer> minQueue = new PriorityQueue<>();
PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());

입력받은 요청을 Split으로 구분 하고 
삽입구문엔 두 큐 모두 데이터 삽입
삭제구문엔 -1과 1을 구분하여 최대 최소값 삭제하고 반대 큐에 같은 값 삭제

for (String str : operations) {
    String[] order = str.split(" ");
    String o = order[0];
    int val = Integer.parseInt(order[1]);
    switch (o) {
        case "I": {
            minQueue.offer(Integer.parseInt(order[1]));
            maxQueue.offer(Integer.parseInt(order[1]));
            break;
        }
        case "D": {
            if (!maxQueue.isEmpty()) {
                if (val == 1) {
                    if (!maxQueue.isEmpty()) {
                        int value = maxQueue.poll();
                        minQueue.remove(value);
                    }
                } else if (val == -1) {
                    if (!minQueue.isEmpty()) {
                        int value = minQueue.poll();
                        maxQueue.remove(value);
                    }
                }
            }
        break;
        }
    }
}

큐가 비었으면 0,0 아니면 최대, 최소값 출력

if (maxQueue.isEmpty()) return new int[]{0, 0};
return new int[]{maxQueue.peek(), minQueue.peek()};

4. 결과

전체코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());

        for (String str : operations) {
            String[] order = str.split(" ");
            String o = order[0];
            int val = Integer.parseInt(order[1]);
            switch (o) {
                case "I": {
                    minQueue.offer(Integer.parseInt(order[1]));
                    maxQueue.offer(Integer.parseInt(order[1]));
                    break;
                }
                case "D": {
                    if (!maxQueue.isEmpty()) {
                        if (val == 1) {
                            if (!maxQueue.isEmpty()) {
                                int value = maxQueue.poll();
                                minQueue.remove(value);
                            }
                        } else if (val == -1) {
                            if (!minQueue.isEmpty()) {
                                int value = minQueue.poll();
                                maxQueue.remove(value);
                            }
                        }
                    }
                    break;
                }
            }
        }

        if (maxQueue.isEmpty()) return new int[]{0, 0};
        return new int[]{maxQueue.peek(), minQueue.peek()};
    }
}