스파르타 알고리즘 트랙 문제 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);     } }

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