[백준 알고리즘] Q11286 절댓값 힙 (우선순위큐)

Priority Queue (우선순위 큐)

 우선순위 큐는 각 각의 원소들이 우선순위를 갖고 있는 큐이다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.

 두 원소의 우선순위가 동일하다면, 먼저 삽입된 원소부터 처리된다. 그리고 우선순위는 아래와 같은 원칙을 가지고 있다.

 1. 모든 정점은 자신의 자식 정점보다 우선순위가 크다. 루트 정점이 가장 큰 우선순위를 가지고 있다.

 2. 완전 이진트리의 형태이다.

 3. 우선 순위가 가장 큰 값이 우선적으로 pop() 된다. (루트정점)

Priority Queue (우선순위 큐) 동작 순서

(1) 삽입

1. 우선순위큐는 완전이진 트리의 형식을 이룬다.	2. '25' 라는 정점이 삽입되면, 완전 이진트리 형식에 맞추어 삽입된다.
3. 정점은 자신의 자식노드보다 우선순위가 커야하기 때문에, 삽입된 정점이     부모 노드보다 우선순위가 크다면 자리를 바꾼다.	4. 삽입된 '25'가 루트 정점의 '17'보다 크기 때문에 자리를 바꾼다.

 (2) 삭제

1. 우선순위 큐는 완전이진트리 형식을 이룬다.	2. 가장 우선순위가 높은 루트 정점이 삭제되고, 우선순위가 가장 낮은       정점이 루트 정점이 된다.
3. 정점은 자신의 자식노드보다 우선순위가 커야하기 때문에, '13' 과       '3'의 자리를 바꾼다.	4. '11'과 '3'도 우선순위에 따라 자리를 바꾼다.

1. Java 구현

           
import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Queue pq = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (Math.abs(o1) > Math.abs(o2) || (Math.abs(o1) == Math.abs(o2) && o1 > o2)) return 1;
                else return -1;
            }
        });

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if(num == 0) sb.append((pq.isEmpty() ? 0 : pq.poll()) + "\n");
            else pq.add(num);
        }

        bw.write(sb.toString());
        bw.close();
    }
}

2. 코드설명

 우선순위 큐를 이용하면 간단하게 해결할 수 있는 문제이다. 결국은 어떤 원소를 가장 우선순위를 높게 만들 것인가?! 라는 우선순위만 잘 정의하면 된다.

 우선순위에 대한 정렬조건을 큐 생성시 부여를 했다. 익명객체를 생성해도 좋지만, 좀더 코드를 간결하게 만들기 위해 람다식을 사용했다.

3. Pain Point

 이 문제를 보고 바로 우선순위 큐를 생각하기가 쉽지는 않았다. 우선순위 큐와 관련된 문제가 백준 알고리즘에 추가적으로 있었다.

 최대힙, 최소힙 문제를 미리 풀었기 때문에 좀더 수월하게 풀지 않았나? 라는 생각이 들었다.