문제

https://www.acmicpc.net/problem/11286
Heap을 사용하면 되는 문제입니다.

풀이

사실 Heap만 알고 있다면, 쉽게 풀 수 있는 문제입니다.

접근 방법

오름차순으로 정렬하고, 절대값이 같을 땐 수를 비교해서 오름차순으로 정렬하면 됩니다.

핵심 원리

자바에서 Heap은 PriorityQueue를 사용하면 되겠죠?
절댓값 비교는 Math 라이브러리를 사용하면 됩니다.
전 Heap에 정렬조건을 람다식을 사용합니다. 정말 편하거든요 ㅎㅎ

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> {
    if (Math.abs(o1) == Math.abs(o2)) { // 절대값이 같다면
        return o1 - o2;
    } else {
        return Math.abs(o1) - Math.abs(o2); // 절대값이 다르다면
    }
});

Heap이 은근 자주 쓰이니까 연습해두면 항상 도움이 됩니다.

전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> {
            if (Math.abs(o1) == Math.abs(o2)) {
                return o1 - o2;
            } else {
                return Math.abs(o1) - Math.abs(o2);
            }
        });

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int number = Integer.parseInt(br.readLine());
            if (number == 0) {
                if (priorityQueue.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(priorityQueue.poll());
                }
            } else {
                priorityQueue.add(number);
            }
        }
    }
}

Reference

x