본문 바로가기

스파르타 알고리즘 트랙 문제(백준)/6일차

스파르타 알고리즘 트랙 문제 6일차 - 1 #1927 최소 힙

문제

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

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

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

 

해결 과정

최대 힙 문제에서 힙의 정렬 순서를 값이 가장 작을 때로 변경한 것과 동일하다.

 

최대 힙 문제와 동일하게 Priority Queue를 사용하되, reverseOrder 구문만 제거해 정순으로 정렬되게 하였다. 그 외에는 최대 힙 문제와 동일한 알고리즘을 구현하였다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

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

            //0 아닐때
            if(x!=0){
                minHeap.offer(x);
            }
            //0일때
            else if(x==0){
                if(!minHeap.isEmpty()){
                    int value = minHeap.poll();
                    sb.append(value).append("\n");
                }
                else{
                    sb.append(0).append("\n");
                }
            }
        }
        System.out.println(sb);
    }
}

이 또한 큰 문제 없이 정답임을 확인하였다.