[BOJ] 11279: 최대 힙 (JAVA)

11279번: 최대 힙

 

Priority Queue (우선순위 큐)

 

FIFO(First In First Out)인 일반적인 Queue와 다르게 Priority Queue는 우선순위가 높은 데이터가 먼저 출력된다.
기본적으로 오름차순 정렬을 하게 되는데 정렬 기준을 바꾸고 싶다면 람다식을 이용하거나 Comparator, Comparable를 이용해야 한다.

 

🏷️ Integer는 Collections.reverseOrder()통해 간단하게 내림차순 정렬 할 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(1);
pq.add(3);
pq.add(7);
pq.add(6);
//pq.offer()도 가능

System.out.println(pq.poll()); // 7 출력

 

package 백준renew;

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

public class 실버2_11279_최대힙 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		StringBuilder sb = new StringBuilder();
		
		int x = Integer.parseInt(br.readLine());
		
		for(int tc=0; tc<x; tc++) {
			int now = Integer.parseInt(br.readLine());
			
			if(now == 0) {
				if(pq.isEmpty()) {
					sb.append(0).append('\n');
				}else {
					int tmp = pq.poll();
					sb.append(tmp).append('\n');
				}
			}else {
				pq.add(now);
			}
		}
		
		System.out.println(sb.toString());
	}
}