백준 1927번 최소 힙(java)

1.문제

📚 우선순위 큐, 자료구조

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

2.풀이

https://velog.io/@syong_e/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%B5%9C%EC%86%8C%ED%9E%99-%EC%B5%9C%EB%8C%80%ED%9E%99 님을 참고했다.

최소 힙이란 완전이진트리 안에서 서로 자리를 바꾸면서 루트노드가 최소값이 되도록하는 형태라면 반대로 최대 힙은 루트노드가 최대값이 되는 형태이다.(스스로 이해한 형태)

최소,최대힙을 구현할 때는 우선순위 큐를 사용한다.

3.코드

package com.example.baekjoon;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> q = new PriorityQueue<>();

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            if (n == 0) {   //  입력이 0이 주어진 경우
                if (q.isEmpty()) {  //  배열이 비어있다면
                    System.out.println(0);
                } else {    //  최소 힙이니 최소 값 출력
                    System.out.println(q.poll());
                }
            } else {    //  x 라면 배열에 추가하는 연산
                q.add(n);
            }
        }
    }
}