BOJ01927 최소 힙

https://www.acmicpc.net/problem/1927 (opens new window)

널리 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하도록 한다.

1. 배열에는 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

PriorityQueue

일반적인 Queue 자료구조는 FIFO 구조로 먼저 들어온 데이터가 먼저 빠져나온다. PriorityQueue는 우선순위를 활용하여 우선순위의 기준에 따라 데이터가 빠져나온다.

PriorityQueue 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다. 큐에 저장될 때 원소를 비교하여 우선순위를 정하기 때문에 비교하기 위한 기준이 있어야 한다.
2. 내부 요소는 이진트리 구조인 힙으로 구성되어 있다. Java의 PriorityQueue는 기본적으로 최소힙으로 구성되어 있다. 즉 우선순위가 낮은 순이다. 또한 힙으로 구성되어 있기 때문에 시간복잡도는 O(NLogN) 이다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ1927 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            if (x == 0 && !priorityQueue.isEmpty()) {
                stringBuilder.append(priorityQueue.poll()).append("\n");
            } else if (x == 0) {
                stringBuilder.append("0\n");
            } else {
                priorityQueue.add(x);
            }
        }

        System.out.println(stringBuilder);
    }
}

#algorithm #BOJ #자료 구조 #우선순위 큐