[BOJ 1927번] 최소 힙 (JAVA)

테크케찰 2020. 9. 7. 23:26

www.acmicpc.net/problem/1927

1927번: 최소 힙

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

www.acmicpc.net

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

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   static int N;
   
   public static void main(String args[]) throws Exception {
	   N=Integer.parseInt(br.readLine());
	   PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
	   
	   for(int i=0;i<N;i++) {
		   int num=Integer.parseInt(br.readLine());
		   if(num==0) {
			   if(pq.isEmpty()) sb.append("0\n");
			   else sb.append(pq.poll()+"\n");
		   }
		   else {
			   pq.add(num);
		   }
	   }
	   System.out.println(sb);
   }
   
}

priority 클래스를 이용해서 문제를 풀어보았습니다.

최소 합을 구하는 문제이므로 오름차순 정렬을 해서 pq에 삽입하면 됩니다.

for문을 통해 입력값이 0일 때 pq가 비어있으면 0을 출력하고, 그렇지 않으면 최소값을 출력했구요, 입력값이 0이 아닐 때, pq에 입력값을 삽입합니다.