BOJ11286 절대값 힙

https://www.acmicpc.net/problem/11286 (opens new window)

절대값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x(x != 0)를 넣는다.
2. 배열에 절대값이 가장 낮은 값을 출력하고, 그 값을 배열에서 제거한다. 절대값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

PriorityQueue

배열에 절대값이 가장 낮은 값을 출력하게 한다(오름차순). 절대값이 가장 작은 값이 여러 개인 경우 가장 작은 수를 출력한다(오름차순).

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> {
    if (Math.abs(o1) < Math.abs(o2)) { // 절대값 기준 오름차순
        return -1;
    // 절대값의 크기가 같은 경우 가장 작은 수 출력
    } else if (Math.abs(o1) == Math.abs(o2) && o1 < o2) { 
        return -1;
    }
    return 1;
});

제출 코드

아래는 최종 제출 코드이다.

import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ11286 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> {
            if (Math.abs(o1) < Math.abs(o2)) {
                return -1;
            } else if (Math.abs(o1) == Math.abs(o2) && o1 < o2) {
                return -1;
            }
            return 1;
        });

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            if (x == 0 && !priorityQueue.isEmpty()) {
                stringBuilder.append(priorityQueue.poll()).append("\n");
            } else if (x == 0) {
                stringBuilder.append("0\n");
            } else {
                priorityQueue.add(x);
            }
        }

        System.out.println(stringBuilder);
    }
}

#algorithm #BOJ #자료 구조 #우선순위 큐