11279번: 최대 힙(Java)

 

 

 가장 큰 값을 출력해야 하므로 우선순위 큐(Priority Queue)를 사용하면 된다.

우선순위 큐는 큐의 일종으로, add()를 할 때 우선순위를 정할 수 있다. 예를 들어 1,4,6,2를 차례대로 오름차순 우선순위 큐에 넣으면 1,2,4,6 순서로 들어가게 된다.

 

 문제에서는 큰 숫자를 먼저 출력하라고 했으므로, 내림차순으로 큐에 들어가게 하면 된다. 우선순위 큐는 기본적(초기화할 때 매개변수가 없다면)으로 낮은 숫자를 우선순위로 하므로, 내림차순으로 큐에 들어가게 하려면 Priority Queue를 초기화할 때 매개변수로

Collections.reverseOrder()

를 넣어주면 된다. Collections에서 제공하는 reverseOrder()로 내림차순으로 저장되게 할 수 있다.

 

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int num;
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
StringBuilder sb = new StringBuilder();

 

 

 

 

 

그러고 나서 숫자를 입력받고 입력받은 숫자가 0이면 큐가 비어있는지 확인 후, 비어있으면 0, 비어있지 않다면 poll()을 출력해 주면 된다. 만약, 입력받은 숫자가 0이 아니라면 큐에 add() 하면 된다.

 

for(int i = 0; i<n; i++)
{
    num = scanner.nextInt();
    if(num == 0)
    {
        sb.append(queue.isEmpty() ? "0" : queue.poll());
        sb.append("\n");
    }
    else
    {
        queue.add(num);
    }
}

 

 

 

 

 

결과 코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int num;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<n; i++)
        {
            num = scanner.nextInt();
            if(num == 0)
            {
                sb.append(queue.isEmpty() ? "0" : queue.poll());
                sb.append("\n");
            }
            else
            {
                queue.add(num);
            }
        }
        System.out.println(sb);
    }
}