BOJ - 최대 힙

개발자-H 2021. 9. 6. 07:42

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

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

최대 힙, 최소 힙은 우선수위큐를 이용하면 풀수 있다.
Number Class를 정의하고 내림차순으로 변경하였다.

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


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

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        PriorityQueue<Number> queue = new PriorityQueue<>();

        while(N-- > 0) {
            Integer number = Integer.parseInt(br.readLine());
            if(number == 0) {
                if(queue.isEmpty()) {
                    System.out.println("0");
                } else {
                    System.out.println(queue.poll().number);
                }
            } else {
                queue.offer(new Number(number));
            }
        }
    }

    public static class Number implements Comparable<Number> {
        private Integer number;

        public Number(Integer number) {
            this.number = number;
        }

        @Override
        public int compareTo(Number other) {
            return other.number - this.number;
        }
    }
}