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

1. 문제

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

11286번: 절댓값 힙

 

2. 풀이

"절댓값으로 배열하되, 절댓값이 같다면 음수부터 배열"하는 것이 문제이다. 따라서 Comparator 인터페이스의 compare 메소드를 오버라이딩 하는 것이 문제의 핵심이다.

Priority Queue

Priority Queue는 힙 구조를 이용해서 만드는데 큰 값이 맨 앞으로 가는 최대힙, 작은 값이 맨 앞으로 가는 최소힙이 있다고 생각하면 된다.

Java에서 PriorityQueue 사용법

최소힙

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

최대힙

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

 

 

3. 코드

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

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

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

		for (int i = 0; i < N; i++) {
			int input = Integer.parseInt(br.readLine());

			if (input != 0) {
				pq.add(input);
			} else {
				if (pq.isEmpty()) {
					System.out.println(0);
				} else {
					System.out.println(pq.poll());
				}
			}
		}
	}
}