[BOJ 11286] 절대값 힙

힙 문제는 대부분 PriorityQueue의 Comparator를 잘 구현하면 풀리는 것 같다.

 

import java.io.*;
import java.util.*;
public class BOJ_11286 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(tk.nextToken());
        Queue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (Math.abs(o1) > Math.abs(o2)) {
                    return 1;
                } else if (Math.abs(o1) < Math.abs(o2)) {
                    return -1;
                } else {
                    return Integer.compare(o1, o2);
                }
            }
        });
        while(N > 0){
            N--;
            tk = new StringTokenizer(in.readLine()," ");
            int x = Integer.parseInt(tk.nextToken());
            if(x == 0){
                //HEAP OUT OR IF == 0 THEN PRINT 0
                if(q.size() == 0){
                    System.out.println(0);
                }else {
                    System.out.println(q.poll());
                }
            }else{
                q.add(x);
            }
        }
    }
}

11286번: 절댓값 힙