[백준] Silver I. 절댓값 힙

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

사용 알고리즘

• 우선 순위 큐

 

풀이

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

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> pq = new PriorityQueue<>((a,b) -> {
            if (Math.abs(a) == Math.abs(b)) {
                return a - b;
            }
            else {
                return Math.abs(a) - Math.abs(b);
            }
        });

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

 

 

회고

 

풀이 자체는 간단했\다. 하지만, 절댓값이 가장 작은 값을 우선순위로 출력하는 부분에서 좀 해맸다.

 

기존 나의 코드는

PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> Math.abs(b) - Math.abs(a));

 

이런식으로 구현했는데 정상적으로 계산이 되지 않았다. 

 

if (Math.abs(a) == Math.abs(b)) {
    return a - b;
}
else {
    return Math.abs(a) - Math.abs(b);
}

 

절댓값이 같을 떄는 작은수를 출력해야 하기 때문에, 이런식으로 케이스를 나눠줘야 한다.