[Java] baekjoon_11279 : 최대 힙

자료 구조, 우선순위 큐

최대 힙 : Silver2

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

11279번: 최대 힙

 

풀이

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    for (int i = 0; i < N; i++) {
      int x = Integer.parseInt(br.readLine());
      if (x > 0) {
        pq.offer(x);
      } else if (x == 0) {
        if (pq.isEmpty()) {
          bw.write("0\n");
        } else {
          bw.write(pq.poll() + "\n");
        } 
      } 
    }
    bw.flush();
    br.close();
    bw.close();
  }
}

 

ㄴ PriorityQueue를 이용했는데, 큐가 비어있지 않을 때 0이 입력되면 가장 큰 값을 출력하고 제거해야되기 때문에 Comparator.reverseOrder()를 이용하도록 했다.

ㄴ PriorityQueue는 우선순위가

 

 

우선순위 큐 (Priority Queue)

PriorityQueue<Integer> pq = new PriorityQueue<>();

우선순위 큐(Priority Queue)는 큐(Queue) 자료구조의 한 종류로, 각 요소마다 우선순위를 가지고 있다.

일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조이다.
하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다.

PriorityQueue 클래스는 기본적으로 작은 값이 우선순위가 높은 방식으로 동작하며, 정수형의 경우 오름차순으로 정렬된다.
또한, 우선 순위 큐는 우선순위가 높은 요소가 먼저 꺼내지는 특징을 가지고 있다.

우선순위 큐는 요소를 추가할 때마다 내부적으로 요소들을 우선순위에 따라 정렬하고, 가장 우선순위가 높은 요소가 큐의 맨 앞에 위치하게 됩니다.
정수형 값을 저장하는 우선순위 큐를 선언할 경우, 정수형 값들을 추가할 때마다 우선순위에 따라 자동으로 정렬되어 관리된다.

이러한 우선순위 큐는 일반적으로 이진 힙(Binary Heap)을 기반으로 구현된다.
힙은 부모 노드가 자식 노드보다 작은(또는 큰) 값을 가지는 이진 트리로, 우선순위 큐의 경우에는 작은 값을 가지는 경우가 일반적이다.

 

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

 

ㄴ PriorityQueue 클래스는 기본적으로 작은 값이 우선순위가 높은 방식으로 동작하며, 정수형의 경우 오름차순으로 정렬된다.

ㄴ 기본적으로 오름차순 정렬이기 때문에 poll()을 이용해서 값을 출력하고 제거할 때, 가장 작은 값이 먼저 출력된다.

ㄴ 가장 큰 값이 먼저 출력하기 위해서는 Comparator.reverseOrder()를 이용해서 내림차순으로 정렬해주어야 한다.