[백준] Silver 1 절댓값 힙

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

 

 

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            int abs1 = Math.abs(a);
            int abs2 = Math.abs(b);
            if (abs1 == abs2) {
                if (a > b) return 1;
                else return -1;
            }
            return abs1 - abs2;
        });

        int n = Integer.parseInt(br.readLine());
        while (n > 0) {
            int x = Integer.parseInt(br.readLine());
            if (x != 0) {
                pq.add(x);
            }

            else {
                if (pq.isEmpty()) {
                    sb.append("0").append("\n");
                }
                else {
                    sb.append(pq.peek()).append("\n");
                    pq.poll();
                }
            }
            n--;
        }
        System.out.println(sb.toString());
    }
}

 

우선순위 큐에 대해서 더 깊게 이해를 하기 위해서 문제를 풀었다. 

 

문제에서  절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 이 부분이 기존의 우선순위 큐 사용과는 달랐다. 이전에는 단순히 숫자의 크기에 따라 우선순위를 정했지만, 이번에는 절댓값이라는 조건이 추가되었기 때문이다.

 

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
    int abs1 = Math.abs(a);
    int abs2 = Math.abs(b);
    return abs1 - abs2;
});

절댓값의 크기 비교는 자바의 Comparator를 사용하여, 각 숫자의 절댓값을 구한 뒤에 작은 숫자를 리턴하도록 구현하였다.

 

하지만, 다른 조건도 고려했어야 했는데, 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 였다.

 

절댓값이 같을 때는, 더 작은 값인 음수를 리턴하는 조건을 추가해야 했다.

if (abs1 == abs2) {
    if (a > b) return 1;
    else return -1;
}