절댓값 힙

문제

풀이

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));
        int n = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> {
            int num1 = Math.abs(o1);
            int num2 = Math.abs(o2);
            
            if(num1 == num2) {
                return o1 > o2 ? 1 : -1;
            } 
            return num1 - num2; // 오름차순으로
        });
        
        for(int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if(num == 0) {
                if(q.isEmpty()) {
                    System.out.println("0");
                } else {
                    System.out.println(q.poll());
                }
            } else {
                q.add(num);
            }
        }
    }
}

절댓값이 가장 작은 값을 출력하도록 하게 하기 위해 우선순위 큐를 생성하면서 오름차순을 디폴트로 하도록 설정한다. 또한, 절댓값이 같은 케이스도 생각해야 하는데 그럴 때는 본래 값이 더 큰 값(양수)이 뒤로 가게 만든다. 그런 다음 for문을 돌리면서 값을 입력 받는데 값이 0인 경우 우선순위 큐가 비어있으면 0을 출력하고 그렇지 않으면 우선순위 큐에 있는 값을 poll 메소드를 이용하여 뽑는다. 여기서 출력되는 값은 우선순위 큐에서 가장 절댓값이 작은 값이다.
그리고 입력 값이 0이 아닌 경우에는 우선 순위 큐에 해당 값을 넣어주면 된다.

결과