[BOJ - JAVA] 11286 - 절댓값 힙(우선순위 큐)

# 주소

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

11286번: 절댓값 힙

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> {
            int x1 = Math.abs(o1);
            int x2 = Math.abs(o2);
            if(x1 == x2)
                return o1 > o2 ? 1 : -1;
            return x1 - x2;
        });
        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if (queue.isEmpty()) {
                    System.out.println("0");
                }else
                    System.out.println(queue.poll());
            }
            else
                queue.offer(x);
        }
    }
}

어제 포스팅한 최소힙, 최대힙 문제와 상당히 흡사하죠?

다만 중요한 것은 Comparator인터페이스를 람다식으로 표현하는데, 어제 포스팅을 보신 분들은 아시겠지만 

https://codingrapper.tistory.com/173

[BOJ - JAVA] 1927, 11279 - 최소 힙, 최대 힙(우선순위 큐)

여기서 new PriorityQueue<>((o1,o2) -> o2 - o1); 이렇게 표현하면 내림차순으로 표현할 순 있습니다.

하지만 문제에서 제시한, 절댓값의 값으로 받으려면 단순히 o1,o2의 비교만 해야할 것이 아니라 절대값순으로 비교해야함을 아실 겁니다.

그렇다면 이 람다식을 조금 더 확장할 필요가 있는데요.

람다식에 익숙하지 않다면 이번 우선순위 큐 문제로 한 번 제대로 이해해보는 것도 좋아보입니다.

int x1 = Math.abs(o1);
int x2 = Math.abs(o2);
if(x1 == x2)
    return o1 > o2 ? 1 : -1;
return x1 - x2;

 

람다식 내부로 들어가기 위해 (o1,o2) -> {

이렇게 내부로 진입하면 x1과 x2를 절댓값으로 치환합니다.

그리고 만약 x1과 x2가 같다면 o1 > o2일 때 1을, 아닐 땐 -1을 return하는데요.

이게 무슨 의미냐면 만약 x1과 x2의 절댓값 크기가 같다면 기본적으로 실제 값이 더 작은 값을 PrioritoyQueue에 담는 것이 목표입니다.

그렇기 때문에 o1 > o2라면 o1이 더 크기 때문에 o2가 우선순위가 높은 큐에 배정되어야 겠죠?

따라서 o1은 1, o2는 -1이라 본다면 o2가 우선순위가 높아지는 것입니다. (먼저 출력이 된다는 의미입니다.)

또한 x1과 x2가 다를 땐 return x1 - x2; 라고 작성하게 되면 오름차순으로 쓸 수 있습니다.

그럼 여기서 의문이 하나 들 수 있습니다.

왜 하필 1과 -1일까요?

알아본 바에 의하면 3 : -3을 쓰든, 1 : -1을 쓰든 큰 차이는 없다고 합니다.

단순히 크기 비교를 위해서 저렇게 양수중 제일 작은 수, 음수 중 제일 작은 수를 갖고와서 비교하는 것으로 보여요.

실험해보니까 다른 수로 해도 문제없이 작동하네요!

감사합니다.