[BOJ/백준][JAVA] 1927 - 최소 힙

[문제]

1927번: 최소 힙

📒 문제

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

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

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

📒 해결 방법

Heap을 구현하는 방법은 Array, ArrayList, PriorityQueue 총 3가지 방법이 있다.
인덱스로 삭제하고 추가를 하는 게 Heap이기 때문에 배열을 사용하는 것도 좋은 방법이지만,
시간제한이 있는 문제였기 때문에 빠르게 Priority Queue로 구현했다

📒 소스코드

package BOJ.Tree;

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

public class boj1927_최소힙 {
    static int N;
    static PriorityQueue<Integer> heap;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        N = Integer.parseInt(br.readLine());

        heap = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(br.readLine());
            if (value == 0) {
                if (heap.isEmpty()) {
                    sb.append("0").append("\n");
                } else {
                    sb.append(heap.poll()).append("\n");
                }
            } else {
                heap.add(value);
            }
        }

        System.out.println(sb.toString());
        br.close();
    }
}

 

📒 리뷰

내제출

 

---

사실 최근에 CS 스터디에서 Heap을 공부한 게 많은 도움이 되었다
보자마자 어떤 알고리즘을 사용해야하는지 바로 알 수 있었기 때문에 구현하는 데에 15분도 걸리지 않았당

👨‍💻Happy New Year👨‍💻