[Java] 백준 11286번 문제 (절댓값 힙)

문제설명

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main 
{
    public static void main(String[] args) throws Exception
    {
    	PriorityQueue<Integer> absHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2)
            {
               if(Math.abs(o1) == Math.abs(o2)) return Integer.compare(o1, o2); //절댓값이 같다면, 더 작은 수를 리턴
               else return Math.abs(o1) - Math.abs(o2); //절댓값이 다르다면, 절댓값이 더 작은 수 리턴
            }
        });
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	int N = Integer.parseInt(br.readLine());
    	for(int i = 0; i < N; ++i)
    	{
    		int input = Integer.parseInt(br.readLine());
    		if(input == 0)
    		{
    			if(absHeap.peek() == null) sb.append(0).append("\n");
    			else sb.append(absHeap.poll()).append("\n");
    		}
    		else absHeap.add(input);
    	}
    	System.out.println(sb.toString());
    }
}

 

설명

2023.10.22 - [Java Category/Java] - [Java] Heap(힙)과 Priority Queue(우선순위 큐)

[Java] Heap(힙)과 Priority Queue(우선순위 큐)

• Priority Queue에서 우선순위의 기준을 다르게 하려면, 비교자(Comparator)를 제공하면 된다.
• 비교자는 Comparator 인터페이스를 구현한 객체를 뜻한다.
• Comparator 인터페이스에는 compare() 메소드가 정의되어 있다.
• 비교자는 이 메소드를 재정의(오버라이딩)해서 비교 결과를 정수 값으로 리턴하면 된다.

리턴 타입	메소드	설명
int	compare(o1, o2)	o1과 o2가 동등하다면 0을 리턴 o1이 o2 보다 우선 순위가 높다면 음수을 리턴 o1이 o2 보다 우선 순위가 낮다면 양수을 리턴

• Integer 클래스의 compare() 정적 메소드도 간단히 설명하겠다.

리턴 타입	설명
int	o1과 o2가 동등하다면 0을 리턴 o1이 o2보다 작다면 음수를 리턴 o1이 o2보다 크다면 양수를 리턴

System.out.println(Integer.compare(1, 2)); //-1
System.out.println(Integer.compare(3, 2)); //1
System.out.println(Integer.compare(100, 2)); //1
System.out.println(Integer.compare(1, 1)); //0

PriorityQueue<Integer> absHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2)
    {
       if(Math.abs(o1) == Math.abs(o2)) return Integer.compare(o1, o2); //절댓값이 같다면, 더 작은 수를 리턴
       else return Math.abs(o1) - Math.abs(o2); //절댓값이 다르다면, 절댓값이 더 작은 수 리턴
    }
});

compare() 오버라이딩 내용은 아래와 같다.

• 힙의 o1과 o2의 절댓값이 같다면, Integer.compare()메소드의 리턴값을 리턴한다.
  Integer.compare()  메소드에서 0을 리턴 받으면 같은 수이다. (예를 들어 1과 1)
  Integer.compare() 메소드에서 음수를 리턴받았으면 o1보다 o2가 더 큰 수이다. (예를 들어 -1과 1)
  Integer.compare() 메소드에서 양수를 리턴받았으면 o1보다 o2가 더 작은 수이다. (예를 들어 1과 -1)
• 힙의 o1과 o2의 절댓값이 다르다면, o1의 절댓값과 o2의 절댓값의 차이를 리턴한다.

compare() 메소드의 리턴 값이
음수라면 o2가 더 크다는 뜻이다. -> o1의 우선순위가 더 높다.
양수라면 o1이 더 크다는 뜻이다. -> o2의 우선순위가 더 높다.
0이라면 서로 같은 수이다. -> o1 와 o2의 우선순위가 같다.