[Java] 백준 - 11286번: 절댓값 힙

9월 5일(화) - 자료 구조 (11286번)

11286번: 절댓값 힙

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 최소 힙 풀이에서 절댓값으로 비교하는 부분만 추가하면 될 것으로 예상

-> Override를 구현할때, Comparator를 활용해야한다는 것을 까먹어서 다시 찾아봐야했었음

-> 복습 필요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

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

import java.util.Comparator;
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> pq = new PriorityQueue<Integer>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int A = Math.abs(o1);
                int B = Math.abs(o2);

                if(A > B)
                {
                    return (A-B);
                }
                else if(A == B)
                {
                    if(o1 > o2)
                    {
                        return 1;
                    }
                    else
                    {
                        return -1;
                    }
                }
                else
                {
                    return -1;
                }
            }
        });

        for(int i=0; i<N; i++)
        {
            int x = Integer.parseInt(br.readLine());

            if(x == 0)
            {
                if(pq.isEmpty())
                {
                    System.out.println("0");
                }
                else
                {
                    System.out.println(pq.poll());
                }
            }
            else
            {
                pq.offer(x);
            }
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ