백준 1927번 최소 힙

최소 힙은 입력받은 데이터를 명령어에 따라 오름차순으로 출력하는 문제다.

 

문제 풀이를 위해 자료 구조 중 우선 순위 큐(Priority Queue)를 사용했다.

 

PrioirityQueue는 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 나가는 것이 아닌 기준에 따라 먼저 우선순위를 결정하고, 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

 

Priority Queue 선언

import java.util.PriorityQueue;
import java.util.Collections;

// 오름차순(낮은 숫자가 먼저) 우선 순위인 Integer형 우선순위 큐 선언
PriorityQueue<Integer> ascendingQueue = new PriorityQueue<>();

// 내림차순(높은 숫자가 먼저) 우선 순위인 Integer형 우선순위 큐 선언
PriorityQueue<Integer> ascendingQueue = new PriorityQueue<>(Collections.reverseOrder());

 

우선 순위 큐를 활용한 풀이 코드

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

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = in.nextInt();

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

        for (int i = 0; i < N; i++) {
            int num = in.nextInt();

            if (num != 0) {
                q.offer(num); // 입력받은 숫자가 0이 아니라면 큐에 삽입
            } else if (q.isEmpty()) {
                sb.append(0).append('\n');
            } else {
                sb.append(q.poll()).append('\n');
            }
        }
        System.out.println(sb);
    }

}