[실버 1] 절댓값 힙

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

11286번: 절댓값 힙

minHeap의 데이터를 Integer가 아닌 Data class {절댓값, 부호}로 해보자

 

minHeap 선언할 때 재정의가 필요하다

 

절댓값 작은 순서가 우선순위)

같을 경우 -부호가 +부호 보다 우선순위)

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

class Data {
    int absolute_value;
    int sign;

    Data(int absolute_value, int sign) {
        this.absolute_value = absolute_value;
        this.sign = sign;
    }
}

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N;

        PriorityQueue<Data> minHeap = new PriorityQueue<>(new Comparator<Data>() {
            @Override
            public int compare(Data o1, Data o2) {
                if (o1.absolute_value == o2.absolute_value)
                    return o1.sign;
                return o1.absolute_value - o2.absolute_value;
            }
        });

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0) {
                if (minHeap.isEmpty())
                    sb.append("0\n");
                else {
                    Data tmp = minHeap.remove();
                    if (tmp.sign < 0)
                        tmp.absolute_value = -tmp.absolute_value;

                    sb.append(tmp.absolute_value+"\n");
                }

            } else {
                if (x > 0)
                    minHeap.add(new Data(x, 1));
                else
                    minHeap.add(new Data(-x, -1));
            }

        }

        System.out.println(sb);
    }
}