[백준 1927 : JAVA] 최소 힙 / PriorityQueue

개요

 

이 문제는 백준 11279 최대 힙 문제와 다른 점이 거의 없다.

자세한 사항이 궁금하면 아래 링크를 참조하면 좋을 것 같다.

Comparator 인터페이스의 compare메소드만 오버라이딩해주면 문제의 풀이는 끝난다.

 

2020/01/26 - [분류 전체보기] - [백준 11279 : JAVA] 최대 힙 / PriorityQueue

[백준 11279 : JAVA] 최대 힙 / PriorityQueue

문제

 

널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

 

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

풀이

 

Comparator 인터페이스의 compare메소드를 오버라이딩해주면 된다.

compare메소드의 구현에 따라 우선순위가 정해지기 때문이다.

 

코드

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

public class Backjoon1927 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x));

        for(int i = 0 ; i < n; i++){
            int val = Integer.parseInt(br.readLine());
            if(val == 0){
                if(queue.isEmpty()) System.out.println("0");
                else System.out.println(queue.poll());
            }else{
                queue.add(val);
            }
        }
    }
}