[백준/11286] 절댓값 힙 (실버 1) JAVA

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

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<NumberPacket> heap = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            if (input == 0) {
                if (heap.isEmpty()) {
                    System.out.println("0");
                } else {
                    NumberPacket poll = heap.poll();
                    System.out.println(poll.originNumber);
                }
            } else {
                heap.add(new NumberPacket(input));
            }
        }
    }

    public static class NumberPacket implements Comparable<NumberPacket>{
        int originNumber;
        int absNumber;

        public NumberPacket(int originNumber) {
            this.originNumber = originNumber;
            absNumber = Math.abs(originNumber);
        }

        @Override
        public int compareTo(NumberPacket o) {
            if (this.absNumber != o.absNumber) {
                return Integer.compare(this.absNumber, o.absNumber);
            }
            return Integer.compare(this.originNumber, o.originNumber);
        }
    }
}

그냥 최소 힙이면 자바 내장 PriorityQueue로 Integer만 저장시키면 되지만 단순히 Integer에서 제시된 Compare비교가 아니기 때문에 따로 원래 값과 절댓 값을 저장하는 클래스를 만들고 Comparable을 구현해야한다.

compareTo 작성법

compareTo의 인자로 들어오는 것은 비교의 대상이다. Integer.compare 메서드는 first 정수가 second 정수보다 작을 경우 음수를 반환한다. 같을 경우 0, 더 크다면 1이다. 자바 내장의 자료구조들은 정렬 알고리즘 작동시 comparable을 활용한다. 정확하게는 compare로직의 리턴인 -1, 0, 1을 확인한다. 이를 통해 자신만의 정렬 알고리즘을 적용한다. 그러므로 프로그래머는 비교인자가 더 작을 경우 -1을 내뱉도록, 같을 경우 0 클 경우 1을 return하도록만 하면 기존의 힙 정렬 알고리즘을 그대로 받아서 사용할 수 있다.

• 정렬에 대한 판단을 문제의 조건에 따라 나누어서 판별한다. 만약 절댓값이 같은 경우 origin값으로 판단하므로 origin에 대한 비교결과를 리턴해야 하므로 오버라이드된 compareTo에 이를 명시하고 그대로 사용해주면 된다.