[백준] 11286번 : 절댓값 힙 (java)

11286번: 절댓값 힙 (acmicpc.net)

11286번: 절댓값 힙

어떻게 생각하고 문제를 풀었는가?

절대값이 가장 작은 값을 출력하고, 절대 값이 가장 작은 값이 여러 개 있을 경우 가장 작은 값을 출력해야 합니다.

0이 입력으로 주어질 때마다 출력을 수행해야 하므로 각 입력에 대해 절댓값과 실제 값을 미리 저장한 후 두 값의 비교를 통해 우선순위를 결정하는 것이 중요하다고 생각하였습니다.

코드

import java.io.*;
import java.util.PriorityQueue;

class Main {
    private static final PriorityQueue<Modulus> priorityQueue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0; i<n; i++){
            int value = Integer.parseInt(reader.readLine());
            if(value != 0){
                priorityQueue.offer(new Modulus(value));
            } else{
                stringBuilder.append(getResult()).append("\n");
            }
        }
        reader.close();
        System.out.println(stringBuilder);
    }

    private static int getResult(){
        return priorityQueue.isEmpty()? 0 : priorityQueue.poll().value;
    }

    private static class Modulus implements Comparable<Modulus>{
        int absolute;
        int value;
        Modulus(int value){
            this.absolute = Math.abs(value);
            this.value = value;
        }

        @Override
        public int compareTo(Modulus o) {
            if(o.absolute == this.absolute){
                return this.value - o.value;
            }
            return this.absolute - o.absolute;
        }
    }
}

우선 순위 큐를 사용하여 코드를 작성하였습니다.

절댓값과 실제 값을 모두 담는 클래스 Modulus를 정의하고, 우선 순위 큐에 삽입함으로써 절댓값과 실제값을 비교하여 우선순위를 결정하도록 하였습니다.

우선 순위 큐에 클래스가 들어가기 위해서는 클래스에 Comparable 인터페이스를 구현하거나, 우선 순위 큐 초기화시에 Comparator를 인자로 생성하여야 합니다.

Comparable 인터페이스를 구현하는 것을 선택하였으며 해당 인터페이스의 compareTo 함수를 Override하였습니다.

compareTo함수는 절댓값이 같을 경우 실제 값의 비교를 하도록 하였고, 그렇지 않을 경우 절댓값의 비교를 통해 해당 객체의 값이 작을 경우 우선순위가 높도록 하였습니다.