15 Mar 2023

[Java] 백준 11279번: 최대 힙

11279

풀이 방법

최대 힙 구현 문제이다.

힙 자료구조는 완전이진트리로 표현할 수 있다.

최대 힙은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙은 부모 노드가 자식 노드보다 같거나 작다.

Priority Heap으로 구현된 PriorityQueue 클래스를 자바에서 지원해주는 덕에 우선순위 큐로 쉽게 문제를 해결하였다.

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class BOJ_11279_최대_힙 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<T; i++) {
			int num = Integer.parseInt(br.readLine());
			
			if(num == 0) {
				if(q.isEmpty()) sb.append(0);
				else sb.append(q.poll());
				
				sb.append("\n");
			} else {
				q.add(num);
			}
		}
		System.out.println(sb);
	}
}

Thank You For Reading

점점 강해지고 있습니다.