[백준] 11286번 : 절댓값 힙 - 자바(JAVA)

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

11286번: 절댓값 힙

 

문제 해석

절댓값이 작은 순서대로 정렬을 해주는 문제입니다.

그리고 가장 작은 순서대로 뽑아내고 절댓값이 동일한다면 음수가 우선순위를 가집니다.

 

문제 풀이 전 설계

PriorityQueue(우선순위 큐)를 활용합니다.

 

또한 Number 클래스를 두고 절대값의 크기(num), 이 수가 음수인지 양수인지를 기록합니다.

 

그리고 절대값의 크기가 같다면 음수가 더 우선순위를 가지며 절대값의 크기가 다르다면 절대값의 크기가 작을수록 우선순위를 가지는 큐를 구현합니다.

 

코드

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

public class Main_11286_절대값힙 {

    static final int POSITIVE = 1;
    static final int NEGATIVE = -1;

    static class Number {
        int num;
        int sign;

        public Number(int num, int sign) {
            this.num = num;
            this.sign = sign;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Number> pq = new PriorityQueue<>(
                (c1, c2) -> c1.num == c2.num ? c1.sign - c2.sign : c1.num - c2.num
        );

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int curNumber = Integer.parseInt(br.readLine());
            int sign = POSITIVE;

            if (curNumber == 0) {
                if (pq.isEmpty()) {
                    sb.append("0\n");
                    continue;
                }

                Number cur = pq.poll();
                int result = cur.num*cur.sign;
                sb.append(result + "\n");
                continue;
            }

            if (curNumber < 0) {
                sign = NEGATIVE;
                curNumber *= -1;
            }
            pq.add(new Number(curNumber, sign));
        }

        System.out.println(sb.toString());


    }
}