[11286번] 절댓값 힙 ( 우선순위 큐 )

✅ 우선 순위 큐

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
			//절대 값이 다르면 작은 거 우선
			int firstAbs = Math.abs(o1);
			int secondAbs = Math.abs(o2);
			//같으면 음수 우선
			if (firstAbs == secondAbs) {
				return o1 > o2 ? 1 : -1;
			}
			return firstAbs - secondAbs;
		});

👾 기본 전제

return 값이 음수일 때 들어오는 값의 순서 유지
return 값이 양수일 때 들어오는 값의 순서 체인지

예를 들어 이해해보자.

o1 = -3, o2 = 3 이 들어왔다면,

절대 값이 같고 o1이 o2보다 작으므로 양수인 1을 리턴시킨다.
이 말인 즉슨 자리 체인지

o1 = 3, o2 = -3 이 들어왔다면,

절대 값이 같고 o1이 o2보다 크므로 음수인 -1을 리턴시킨다.
이 말인 즉슨 자리 유지

o1 = -4, o2 = 5 이 들어왔다면,

절대 값이 다르고 o1이 o2보다 작으므로 음수인 4-5(-1)을 리턴시킨다.
이 말인 즉슨 자리 유지

o1 = 5, o2 = -4 이 들어왔다면,

절대 값이 다르고 o1이 o2보다 크므로 양수인 5-4(1)을 리턴시킨다.
이 말인 즉슨 자리 체인지

✅ 코드

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 IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int input = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
			//절대 값이 다르면 작은 거 우선
			int firstAbs = Math.abs(o1);
			int secondAbs = Math.abs(o2);
			//같으면 음수 우선
			if (firstAbs == secondAbs) {
				return o1 > o2 ? 1 : -1;
			}
			return firstAbs - secondAbs;
		});

		for (int i = 0; i < input; i++) {
			int request = Integer.parseInt(br.readLine());
			if (request == 0) {
				if (queue.isEmpty()) {
					System.out.println("0");
				} else {
					System.out.println(queue.poll());
				}
			} else {
				queue.add(request);
			}
		}

	}
}