[우선순위 큐] 백준 11286번 절댓값 힙(Java)

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

📚 문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

입력에서 0이 주어진 회수만큼 답을 출력한다.

만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

📝 문제 해결

절댓값이 작은 순 ▶️ 숫자가 작은 순으로 출력해야 하므로 PriorityQueue 선언 시 Comparator의 compare를 오버라이딩하여 정렬 기준에 맞게 수정해주면된다.

1. 절댓값이 같으면, 작은 수 먼저 출력
2. 절댓값이 같지 않으면, 절댓값이 작은 수 출력

 

💻 코드

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class BOJ11286 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) ->
                Math.abs(o1) == Math.abs(o2) ? Integer.compare(o1, o2) : Integer.compare(Math.abs(o1), Math.abs(o2))
        );

        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                if (queue.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(queue.poll());
                }
            } else {
                queue.offer(n);
            }
        }
    }
}