[Java] 11286 절댓값 힙

문제

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

배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 
절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

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

입력되는 정수는 -231보다 크고, 231보다 작다.

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

문제 풀이

아래 최소 힙과 비슷한 문제이다. 다만 Comparator를 활용하여 정렬 우선순위를 설정할 수 있느냐를 묻는다.

PriorityQueue에서 (o1, o2) 에 대한 compare함수를 재정의한다. (o1은 큐의 최상위 값, o2는 새로 넣을 값)

compare에서는 A  B 두 값을 비교할 때 왼쪽 값 이 크면 1, 오른쪽 값이 크면 B, 같으면 0을 출력한다.

두 값의 절대 값이 같을 때 두 값을 비교하여 o1이 크면 1(o1이 큰 값으로 판단되어 o2가 우선순위를 갖는다.)  o2 가 크면 -1로 설정한다.

 

절대 값이 같지 않은 경우에는 두 절대 값을 빼서 나온 값을 이용한다.

[Java] 1927 최소 힙

 

자바 코드

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

public class N11286 {
    public static void main(String[] args) throws IOException {
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> {
            int one = Math.abs(o1);
            int two = Math.abs(o2);

            if(one == two){
                return o1 > o2 ? 1 : -1;
            }else{
                return one - two;
            }
        });

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