java/ 백준 11286 절댓값 힙

 

문제

11286번: 절댓값 힙

 

문제

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

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

 

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

 

 

---

 

코드

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 N = Integer.parseInt(br.readLine());

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

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(br.readLine());
            if (now == 0) {
                if (!queue.isEmpty()) {
                    sb.append(queue.poll()).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            } else queue.add(now);
        }

        System.out.println(sb);

    }
}

 

풀이 시도

1. 값이 들어올 때마다 기준에 따라 정렬되어야 한다 → PriorityQueue를 사용해야겠다고 생각했다.

2. 기존의 PriorityQueue는 natural order를 구현하는 Comparator를 사용한다.

3. 선언 시 PriorityQueue​(Comparator<? super E> comparator)에 따라 comparator를 구현하자

 

풀이 

PriorityQueue 선언 시 comparator 구현

PriorityQueue<Integer> queue = new PriorityQueue<>(
        (o1, o2) -> {
            if (Math.abs(o1) == Math.abs(o2)) { //절댓값이 같은 경우
                return o1 > o2 ? 1 : -1;
                //o1이 더 크다면 양수 반환 -> o1과 o2의 자리를 바꾼다
                //o1이 더 작다면 음수 반환 -> 지금의 자리를 유지한다
            } else { //절댓값이 같지 않은 경우 절댓값이 작은 순서로 정렬한다
                return Math.abs(o1) - Math.abs(o2); 
                //양수가 반환되면 o1의 절댓값이 더 큰 경우이다 -> o2, o1순으로 정렬
                //음수가 반환되면 o2의 절대값이 더 큰 경우이다 -> o1, o2 유지
            }
        }
);

 

PriorityQueue를 통해 요청사항 수행

for (int i = 0; i < N; i++) {
    int now = Integer.parseInt(br.readLine());
    if (now == 0) { //0을 입력받은 경우
        if (!queue.isEmpty()) {
            sb.append(queue.poll()).append("\n");
        } else {
            sb.append(0).append("\n");
        }
    } else queue.add(now); //0을 입력받지 않은 경우
}

System.out.println(sb); //연산 종료 후 출력