[백준_JAVA_알고리즘] 11286 절댓값 힙 #힙 #우선순위 큐

힙 문제는 우선순위 큐를 이용해서 해결할 수 있습니다.

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 bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(Math.abs(o1) == Math.abs(o2)) return o1 - o2;
                else return Math.abs(o1) - Math.abs(o2);
            }
        });

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

            if(x == 0) {
                int out = priorityQueue.isEmpty() ? 0 : priorityQueue.poll();
                System.out.println(out);
            }
            else priorityQueue.offer(x);
        }
    }
}

 

 x == 0이라면, 힙에서 가장 작은 절댓값을 출력하고 제거합니다. 만약 절댓값이 같은 값이 여러 개라면, 값이 더 작은 정수를 출력합니다. 힙이 비어있으면 0을 출력합니다.

x != 0이라면, x를 힙에 추가합니다.

 

PriorityQueue는 기본적으로 오름차순 정렬이므로, Comparator를 오버라이딩하여 정렬을 커스터마이징 합니다.

 

compare 메서드에서 절댓값을 비교하여 정렬합니다.

if (Math.abs(o1) == Math.abs(o2)) return o1 - o2;

절댓값이 같은 경우, 실제 값의 크기를 기준으로 정렬합니다.

else return Math.abs(o1) - Math.abs(o2);

절댓값이 다를 경우, 절댓값이 작은 값을 우선순위로 정렬합니다.

 

Comparator에 대한 설명은 아래에서 확인할 수 있습니다.

https://akong2125.tistory.com/entry/JAVA-Comparator-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

[Java] Comparator 이해하기

 

 

if문과 for문을 통해 연산 처리를 합니다.

int out = priorityQueue.isEmpty() ? 0 : priorityQueue.poll();

힙이 비어 있다면 0을 출력, 그렇지 않다면 힙의 우선순위가 가장 높은 값을 출력합니다.

 

내부 동작은 다음과 같습니다.

1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0

• 1 추가 → 힙 상태: [1]
• -1 추가 → 힙 상태: [-1, 1] (절댓값이 같으면 작은 값이 우선)
• 0 명령어 → 출력: -1, 힙 상태: [1]
• 0 명령어 → 출력: 1, 힙 상태: [] (비어 있음)
• 0 명령어 → 출력: 0 (힙 비어 있음)
• 1 추가 → 힙 상태: [1]
• 1 추가 → 힙 상태: [1, 1]
• -1 추가 → 힙 상태: [-1, 1, 1]
• -1 추가 → 힙 상태: [-1, -1, 1, 1]
• 2 추가 → 힙 상태: [-1, -1, 1, 1, 2]
• -2 추가 → 힙 상태: [-1, -1, -2, 1, 2, 1]
• 0 명령어 → 출력: -1, 힙 상태: [-1, 1, -2, 1, 2]
• 0 명령어 → 출력: -1, 힙 상태: [-2, 1, 1, 2]
• 0 명령어 → 출력: -2, 힙 상태: [1, 2, 1]
• 0 명령어 → 출력: 1, 힙 상태: [1, 2]
• 0 명령어 → 출력: 1, 힙 상태: [2]
• 0 명령어 → 출력: 2, 힙 상태: []
• 0 명령어 → 출력: 0 (힙 비어 있음)

 

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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