[Python][C++] 1927번 최소 힙

문제

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

 

 

코드

1. Python

import sys
import heapq

input = sys.stdin.readline

heap = []

for _ in range(int(input())):
    x = int(input())
    if x:
        # x가 0이 아니면 힙에 x를 추가
        heapq.heappush(heap, x)
    else:
        # x가 0이면 힙에서 최솟값을 제거하고 출력
        # 만약 힙이 비어있으면 0을 출력
        print(heapq.heappop(heap) if heap else 0)

 

2. C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;

    // 입력: 처리할 명령의 수
    cin >> n;

    // 우선순위 큐(최소 힙) 생성
    priority_queue<int, vector<int>, greater<int>> minHeap;

    while (n--) {
        int x;

        cin >> x;

        if (x == 0) {
            // x가 0인 경우, 최소 힙에서 최솟값을 출력하고 제거
            if (minHeap.empty())
                cout << 0; // 힙이 비어있으면 0을 출력
            else {
                cout << minHeap.top(); // 최솟값 출력
                minHeap.pop();         // 최솟값 제거
            }
            cout << "\n"; // 개행 출력
            continue;
        }
        // x가 0이 아닌 경우, 숫자를 최소 힙에 추가
        minHeap.push(x);
    }

    return 0;
}

 

 

풀이 

최소 힙을 구현하는 문제

 

 

우선순위 큐 참고

https://ehdbs0903.tistory.com/entry/Data-Structure-우선순위-큐Priority-Queue와-힙Heap

[Data Structure] 우선순위 큐(Priority Queue)와 힙(Heap)