백준(BOJ) 11286 : 절댓값 힙

 

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

우선순위큐는 데이터를 넣거나 삭제 할때 logN의 시간복잡도를 가지므로 연산의 개수가 10만개 이므로 NlogN의 시간복잡도를 가지는 것.

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

public class Main{
    public static class Element{
        int original;
        int ab;
        public Element(int original){
            this.original=original;
            this.ab=Math.abs(original);
        }
        public int getAbsValue(){
            return ab;
        }
        public int getOriginal(){
            return original;
        }
    }
    public static void solution(int[]arr, int n){
        PriorityQueue<Element>pq=new PriorityQueue<>(Comparator.comparing(Element::getAbsValue).thenComparing(Element::getOriginal));
        for(int i=0;i<n;++i){
            if(arr[i]!=0){
                pq.add(new Element(arr[i]));
            }
            else{
                if(pq.isEmpty())
                    System.out.println(0);
                else {
                    int output = pq.poll().original;
                    System.out.println(output);
                }
            }
        }
    }
    public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[]arr=new int[n];
        for(int i=0;i<n;++i){
            arr[i]=Integer.parseInt(br.readLine());
        }
        solution(arr,n);
    }
}