[백준] 7662번 - 이중 우선순위 큐 (Gold 4)

문제 링크

백준 7662번 - 이중 우선순위 큐 (Gold 4)

문제 설명

이중 우선 순위 큐를 구현하는 문제이다.
가장 높은 우선 순위/가장 낮은 우선 순위를 각각 제거하는 기능이 필요하다.

정답 코드 및 설명

우선 순위 큐를 공부했다면 당연한거지만, 최대 힙과 최소 힙 두개를 모두 사용하면 된다.
문제는 최대 힙에서는 최솟값을 제거하는 일이 어렵고, 반대도 마찬가지이다.
이는 현재 이중 우선 순위 큐에 들어있는 원소의 값과 그 개수로 이루어진 map을 활용해서 처리했다.
최소값을 구하기 위해 최소 힙에서 원소를 꺼낼 때 이미 앞에서 제거된 값이 나온다면 다음 원소를 가져오는 방식이다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        int k;
        String command;
        DoublePriorityQueue queue;
        for (int i = 0; i < t; i++) {
            k = Integer.parseInt(br.readLine());
            queue = new DoublePriorityQueue();
            for (int j = 0; j < k; j++) {
                command = br.readLine();
                queue.command(command);
            }
            queue.print();
            bw.write(queue.sb.toString());
        }
        bw.close();
    }

}

class DoublePriorityQueue {
    int capacity, size;
    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;
    HashMap<Integer, Integer> map;
    StringBuilder sb;

    DoublePriorityQueue() {
        this.minHeap = new PriorityQueue<>();
        this.maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        this.map = new HashMap<>();
        this.size = 0;
        this.sb = new StringBuilder();
    }

    public void command(String command) {
        String commandSplit[] = command.split(" ");
        char op = commandSplit[0].charAt(0);
        int x = Integer.parseInt(commandSplit[1]);
        if (op == 'I')
            this.insert(x);
        if (op == 'D')
            this.delete(x);
    }

    private void insert(int x) {
        size++;
        minHeap.add(x);
        maxHeap.add(x);
        map.put(x, map.getOrDefault(x, 0) + 1);
    }

    private int delete(int x) {
        if (size == 0 || x != -1 && x != 1) // 비어있는 경우
            return 0;
        size--;
        if (x == -1) { // 최소값 삭제
            int min = minHeap.poll();
            // 이미 제거된 값을 가져왔다면 다음 값 가져오기
            while (map.get(min) == 0) {
                min = minHeap.poll();
            }
            // 현재 원소의 개수 재설정
            map.replace(min, map.get(min) - 1);
            return min;
        } else { // 최대값 삭제
            int max = maxHeap.poll();
            while (map.get(max) == 0) {
                max = maxHeap.poll();
            }
            map.replace(max, map.get(max) - 1);
            return max;
        }
    }

    public void print() {
        if (this.size == 0)
            sb.append("EMPTY\n");
        else {
            int max = this.delete(1);
            int min;
            if (this.size == 0)
                min = max;
            else
                min = this.delete(-1);
            sb.append(max).append(' ').append(min).append('\n');
        }
    }
}