[Baekjoon Online Judge] 백준 1927번 최소 힙(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1927번 최소 힙

(C++, Python)

(글쓴날 : 2020.04.25)

 

---

* Baekjoon Online Judge, 백준 1927번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1927번 최소 힙

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1927

1927번: 최소 힙

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

N개만큼 주어지는 정수의 값에 따라 만약, 자연수라면 해당 값을 저장하고, 0이라면 저장되어 있는 수 중 가장 작은 값을 출력 후 제거하는 최소 힙을 구현하는 문제입니다.

 

저의 경우, C++과 Python을 사용했으며 각 언어 별로 지원하는 우선순위 큐 컨테이너를 이용해 문제를 해결했습니다. (Python의 경우 힙큐로 구현했습니다.)

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <functional>
#include <queue>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio;
    cin.tie(0);
    cout.tie(0);
 
    int N;
    cin >> N;
 
    priority_queue<int, vector<int>, greater<int>> pq;
 
    int value = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> value;
 
        if (!value)
        {
            try
            {
                if (!pq.size())
                    throw 0;
                cout << pq.top() << "\n";
                pq.pop();
            }
            catch (int e)
            {
                cout << e << "\n";
            }
        }
        else
            pq.push(value);
    }
 
    return 0;
}

---

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
N = int(input())
hq = []
 
for _ in range(N):
    value = int(input())
 
    if not value:
        try:
            print(heapq.heappop(hq))
        except:
            print(0)
    else:
        heapq.heappush(hq, value)

---