[백준] 11279번. 최대 힙 (JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;

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> sortedNumbers = new PriorityQueue<>(Comparator.reverseOrder());

        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(sortedNumbers.isEmpty()){
                    System.out.println(0);
                }else{
                    System.out.println(sortedNumbers.poll());
                }
            }else{
                sortedNumbers.offer(x);
            }
        }

    }
}

최소 힙 문제와 동일하게 우선순위 큐를 사용하되 역순으로 정렬해 주는 Comparator.reverseOrder()를 사용하여 내림차순 정렬을 해주면 된다.
여기서는 단순히 Comparator.reverseOrder()를 사용하여 우선순위 큐의 정렬을 바꾸었지만 람다식을 통해서도 사용이 가능하다. 

PriorityQueue<Integer> sortedNumbers = new PriorityQueue<>(Comparator.reverseOrder());

PriorityQueue<Integer> sortedNumbers = new PriorityQueue<>((o1, o2) ->{
    return o1 > o2 ? -1 : 1;
} );

 

위의 코드와 아래 코드는 동일하게 동작한다. 람다식을 해석하면 이러한 순서로 동작한다.

1. o1과 o2를 설정한다. o1, o2 순대로 o1이 정렬했을 때 앞에 오는 것이라고 생각하면 된다.

2. o1이 o2보다 크다면 -1을 작거나 같다면 1을 반환한다.

3. 우선순위 큐의 람다식은 양수가 반환 되었을 때(즉, 1과 -1이 아닌 임의의 수를 둬도 된다.) 순서를 변경하고, 음수가 반환된다면 순서를 변경하지 않는다.

4. o1 > o2 일 경우 음수를 반환하므로 순서를 변경하지 않고 내림차순 배열이 가능해진다.

우선순위 큐의 람다식을 다루는 부분은 매우 중요하고 적재적소에 활용할 줄 알아야 하므로 백준 11286 번을 추가적으로 풀며 손에 익히면 좋을 것 같다.