백준 11286 절댓값 힙 (Java)

1. 문제 링크

11286번: 절댓값 힙

 

2. 문제 및 입출력예제

 

3. 문제 풀이

절댓값 힙이라는 문제 이름에서 알 수 있듯이 PriorityQueue를 이용했다.

 

절댓값이기 때문에 익명클래스를 이용해 Comparator로 비교하는 과정을 만들었다.

입력받은 값을 큐에 추가를 하는 과정에서 비교를 하게 된다.

기존 compare을 사용하는 방식을 유지하지만 절댓값이 같은 경우 작은 값이 우선순위가 되도록 했다.

 

4. 코드

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

public class Main {
	private static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() { 
			@Override
			public int compare(Integer o1, Integer o2) {
				int temp = Math.abs(o1)-Math.abs(o2);
				if(temp == 0) {
					temp = o1-o2;
				}
				return temp;
			}
		});
		
		int N = Integer.parseInt(br.readLine());
		for(int i=0;i<N;i++) {
			int x = Integer.parseInt(br.readLine());
			if(x == 0) { //출력
				//절댓값이 가장 작은 값 출력
				if(queue.size() == 0) {
					sb.append(0).append("\n");
				}
				else {
					sb.append(queue.poll()).append("\n");
				}
			}
			else { //추가
				queue.offer(x);
			}
		}

		System.out.println(sb);
	}
}