[BOJ] 11279. 최대 힙 Python, Java

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

11279번: 최대 힙

 

 

1. 해결방법

heapq 우선순위 큐 문제이다.

python 의 우선순위 큐가 있는지는 공부 역량이 부족해서 잘 모르지만, heapq로도 가능하다.


1. heap이라는 리스트를 빈 값으로 생성.
2. 입력받은 정수 x가 0이 아닌 정수라면, heap에 삽입.
3. 삽입할 때, 문제의 목적이 최대 값을 뽑아야 하므로 -x를 삽입한다.
4. x가 0일 때, heap이 빈 상태라면 0을 print
5.  heap이 빈 상태가 아니라면, heappop(heap)을 하는데 음수로 바꿔서 출력.
 -> [-2, -1] 이라면 heappop(heap)를 했을 때, -2가 출력되겠지만 여기서 음수로 바꿔주어서 2가 출력된다. 즉, 최대 값이 출력.

 

 

2. 정답코드 Python

import sys
import heapq

input = sys.stdin.readline

N = int(input())
heap = []
for _ in range(N):
    x = int(input())
    if x == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, -x)

 

3. 정답코드 Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;


public class Test {
	static int N;
	static int x;
	static PriorityQueue<Integer> heap = new PriorityQueue<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			x = Integer.parseInt(br.readLine());
			if (x == 0) {
				if (heap.isEmpty()) {
					System.out.println(0);
				}
				else {
					System.out.println(-heap.poll());
				}
			}
			else {
				heap.add(-x);
			}
		}
	}
	

}