[백준] 11279 최대 힙 - Java / Python

 

 

 

힙 자료구조를 사용해서 푸는 문제다.

힙을 사용해서 우선순위 큐를 구현해 풀자.

 

구현은 어렵지 않기 때문에 힙을 알고 있으면 쉽게 풀 수 있고, 모르면 힘들게 풀거나 틀리는.. 문제이다.

 

Java

 

우선순위 큐의 기본 값은 최소 힙이기 때문에 Collections.reverseOrder()를 인자에 넣어 최대 힙으로 바꿔주자.

 

힙 자료구조를 몰라도 유틸을 사용하면 풀 수 있지만.. 이번 기회에 이론도 제대로 잡고 가자.

 

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

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));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

		for(int i=0; i<N; i++){
			int command = Integer.parseInt(br.readLine());

			if(command == 0){
				if(q.isEmpty()){
					sb.append(0).append('\n');
				}else{
					sb.append(q.poll()).append('\n');
				}
			}else{
				q.offer(command);
			}
		}

		System.out.println(sb);




	}
}

 

Python

 

파이썬에서도 힙 모듈을 지원한다.

 

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

 

최소 힙을 최대 힙으로 활용할 때는 위 블로그를 참고했다.

 

import heapq
import sys

N = int(input())
heap = []

for i in range(N):
    command = int(sys.stdin.readline())
    if command == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, (-command, command))