백준 11286번 절댓값 힙

대표적인 자료구조 활용 문제이다.

문제를 해결하기 위해서는 다음과 같은 사고와 판단이 필요하다고 생각한다.

1. 절댓값이 작은 숫자부터 출력해야 하므로 우선순위 큐라는 자료구조를 사용해야 한다.
2. 우선순위 큐를 적절히 활용하여 절댓값이 작은 순서대로 순위를 매겨야 한다.

우선순위 큐의 활용을 묻는 문제기에 엄청나게 복잡하지는 않다.

풀이 방식은 우선순위 큐를 직접 구현하는 경우가 아니라면 두 가지로 나뉘는 것 같다.

1. 우선순위 큐의 요소 순서를 절댓값으로 판단하여 작은 순서대로 배치
2. 우선순위 큐를 두 개 사용하여 절댓값 계산을 통해 요소 출력

필자는 2번 방식으로 풀었다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 빠른 입,출력을 위한 BufferedReader와 StringBuilder 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> positive_pq = new PriorityQueue<>();                          // 양수를 저장할 우선순위 큐
        PriorityQueue<Integer> negative_pq = new PriorityQueue<>(Comparator.reverseOrder()); // 음수를 저장할 우선순위 큐
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());

            if (x == 0) { // 큐에서 절댓값이 가장 작은 요소를 출력해야 할 때
                if (!positive_pq.isEmpty() && !negative_pq.isEmpty()) { // 양수 큐, 음수 큐에 모두 숫자가 있을 경우
                    int negative = negative_pq.peek();

                    // 음수 큐의 최솟값, 양수 큐의 최솟값을 비교해서 더 작은 숫자를 출력(만약 두 숫자가 똑같다면 음수를 출력)
                    if (Math.abs(negative) <= positive_pq.peek()) {
                        sb.append(negative_pq.poll());
                    } else {
                        sb.append(positive_pq.poll());
                    }
                } else if (!positive_pq.isEmpty()) { // 음수 큐는 비어있을 때
                    sb.append(positive_pq.poll());
                } else if (!negative_pq.isEmpty()) { // 양수 큐가 비어있을 때
                    sb.append(negative_pq.poll());
                } else {
                    sb.append(0);
                }
                sb.append("\n");
            } else { // 큐에 숫자를 삽입할 때
                // 주어진 숫자의 절댓값과 주어진 숫자를 비교해서 같을 경우 양수 큐에 삽입, 다를 경우 음수 큐에 삽입
                if (x == Math.abs(x)) {
                    positive_pq.add(x);
                } else {
                    negative_pq.add(x);
                }
            }
        }

        System.out.println(sb);
    }
}