BOJ_11286 : 절댓값 힙

👉 문제링크

11286번: 절댓값 힙

---

---

🔸 문제 분석 🔸

• n의 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 풀 수 있다.
• 데이터가 삽입 될 때마다 절댓값으로 정렬되는 우선순위 큐를 사용한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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> queue = new PriorityQueue<>((o1, o2) -> {
           int first_abs = Math.abs(o1);
           int second_abs = Math.abs(o2);
           if (first_abs == second_abs)
               return o1 > o2 ? 1 : -1;         //절댓값이 같으면 음수 우선 정렬하기
           else
               return first_abs - second_abs;   //절댓값을 기준으로 정렬하기(음수면 뒤쪽이 큐에서 더 앞쪽)
        });
        for (int i = 0; i < n; i++) {
            int order = Integer.parseInt(br.readLine());
            if (order == 0) {
                if (queue.isEmpty()) System.out.println("0");
                else System.out.println(queue.poll());
            }
            else queue.add(order);
        }
    }
}

🔸 코드 해석 🔸

• 우선순위 큐의 정렬 조건을 직접 정의한다.
  • 양수를 반환하면 o1, 음수를 반환하면 o2의 우선순위가 더 높아진다.
  • 절댓값이 같으면 음수의 우선순위를 더 높인다.
  • 절댓값이 다르다면 절댓값 기준으로 정렬한다.
• n개의 연산을 입력받아 우선순위 큐에 사용한다.
  • 0을 입력 받았을때 우선순위 큐가 비었으면 "0"출력
    • 아니면 가장 높은 우선순위 원소 출력
  • 0이 아니면 그 수를 우선순위 큐에 넣음

---

🔸 end 🔸

• 우선순위 큐를 사용하는건 문제를 보고 보고 알아챘지만 java로 어떻게 구현해야하는지 막막했다.
• 절댓값 기준으로 직접 정의하는 방법이 매우 생소해서 좋은 공부가 되었다.