[백준] 11286번 - 절댓값 힙

 

https://ddamdoo.tistory.com/162

[백준] 11279번 - 최대 힙

https://ddamdoo.tistory.com/163

[백준] 11279번 - 최대 힙

 

위 두개의 최대, 최소 힙의 응용 문제이다. 정렬을 하되 comparator를 이용하여서 정렬의 기준을 재 정의해야 한다. 만약 절댓값이 더 작으면 우선순위가 있고, 절댓값이 같으면 더 작은 값에 우선순위가 있도록 한다. 그저 절댓값이 높은 숫자에만 신경쓰면 안되고, 절댓값이 같지만 다른 경우도 포함해야 한다.

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

public class p11286 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b) {
				if (Math.abs(a) > Math.abs(b) || Math.abs(a) == Math.abs(b) && a > b) {
					return 1;
				} else {
					return -1;
				}
			}
		});
		int a = Integer.parseInt(br.readLine());

		for (int i = 0; i < a; i++) {
			int b = Integer.parseInt(br.readLine());
			if (b == 0) {
				if (pq.isEmpty()) {
					System.out.println(0);
				} else {
					System.out.println(pq.poll());
				}
			} else {
				pq.add(b);
			}
		}
	}
}