[백준] 11279 최대 힙 - 우선순위큐(PriorityQueue) JAVA

https://www.acmicpc.net/problem/11279

코드설명

우선순위큐를 활용합니다.

 

유의할점은, 최대 힙이기 떄문에 Collections.reverseOrder로 처리하면 최대힙으로 자동으로 변환됩니다.

우선순위큐의 시간복잡도입니다.

삽입/삭제/poll()/remove() 시에는 O(log n)
peek()/element(): O(1)

contains(element): O(n) ( 특정 요소가 존재하는지 확인하려면 선형 탐색이 필요하므로, 선형 시간 복잡도가 소요됩니다. )
remove(element) 또는 indexOf(element): O(n) (특정 요소를 제거하거나 인덱스를 찾으려면 선형 탐색이 필요하므로, 선형 시간 복잡도가 소요됩니다. )

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		while(N-- > 0) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			if(x == 0) {
				if(pq.isEmpty()) System.out.println(0);
				else System.out.println(pq.poll());
			}
			else {
				pq.add(x);
			}
		}
		
	}
}