[백준] 우선순위 큐 - 11286번 절댓값 힙

문제

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

11286번: 절댓값 힙

 

풀이

최대힙과 최소힙에 이어서 또다른 우선순위큐 문제이다.

입력값 자체가 아니라 입력값의 절댓값이 비교 기준이 되는데 이를 구현하기 위해 compare를 오버라이딩하여 구현하였다.

PriorityQueue<Integer> q = new PriorityQueue<>(
				(o1, o2) -> Math.abs(o1) == Math.abs(o2) ? Integer.compare(o1, o2)
						: Integer.compare(Math.abs(o1), Math.abs(o2)));

절댓값이 같은 경우 원래 숫자를 비교하고 절댓값이 다른 경우 절댓값끼리 비교해 준다.

 

코드

package 우선순위큐;

import java.util.*;

public class No11286_절댓값힙 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		PriorityQueue<Integer> q = new PriorityQueue<>(
				(o1, o2) -> Math.abs(o1) == Math.abs(o2) ? Integer.compare(o1, o2)
						: Integer.compare(Math.abs(o1), Math.abs(o2)));

		for (int i = 0; i < N; i++) {
			int num = sc.nextInt();
			if (num == 0) {
				if (q.isEmpty())
					System.out.println(0);
				else {
					System.out.println(q.poll());
				}
			} else {
				q.add(num);
			}

		}

	}

}