백준 11279번: 최대 힙

문제

문제 바로가기> 백준 11279번: 최대 힙

풀이

최소 힙을 최대 힙으로 바꿔 주기 위해 (-x, x) tuple을 집어 넣었다.

def solution():
    import sys, heapq
    input = sys.stdin.readline
    heap = []
    n = int(input())
    for _ in range(n):
        x = int(input())
        if x:
            heapq.heappush(heap, (-x, x))
        else:
            if len(heap) == 0:
                print(0)
            else:
                print(heapq.heappop(heap)[1])
solution()

코드 개선

그런데 생각해보니 굳이 tuple을 집어 넣지 않고, x의 마이너스 값을 집어 넣은 후에 출력할 때 마이너스만 붙쳐주면 메모리와 시간을 절약할 수 있었다.

def solution():
    import sys, heapq
    input = sys.stdin.readline
    heap = []
    n = int(input())
    for _ in range(n):
        x = int(input())
        if x:
            heapq.heappush(heap, (-x))
        else:
            if len(heap) == 0:
                print(0)
            else:
                print(-heapq.heappop(heap))
solution()

C++을 이용한 풀이

priority queue를 이용하여 쉽게 풀 수 있다.

#include<iostream>
#include<queue>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    priority_queue<int> pq;
    int n; cin>>n;
    for(int i=0; i<n; i++){
        int tmp; cin>>tmp;
        if(tmp == 0){
            if(pq.empty()) cout << 0 << '\n';
            else {
                int top = pq.top(); pq.pop();
                cout << top << '\n';
            }
        }
        else pq.push(tmp);
    }
}