널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
heap 이라는 자료구조 형을 이용하여 답을 내는 문제
문제 풀이
과거에 Python으로 풀었던 문제였는데, C++ 로 한번 더 풀게 됐다.
Python에는 heap 이라는 내장함수가 존재하여 그걸로 풀었고 C++ 에는 Queue 헤더에 priority_queue 가 heap 과 같은 역할을 해 그것을 사용했다.
C++ 에서 제공하는 내장함수는 Max Heap 이여서 각 숫자에 - 를 붙여 최소값이 top에 존재할 수 있게 했다.
Heap
완전 이진 트리의 일종
삽입과 삭제가 모두 $ O(logN) 인 자료구조 이다.
Max Heap 은 가장 큰 수가 루트노드에 존재하고 Max Heap은 최소값이 루트노드에 존재한다.
C++ 코드
#include <bits/stdc++.h>
using namespace std;
int main () {
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int N;
cin >> N;
priority_queue<int> q;
for (int i=0; i<N; i++) {
int tmp;
cin >> tmp;
if (tmp==0 && !q.empty()) {
cout << -q.top() << "\n";
q.pop();
} else if (tmp == 0) {
cout << 0 << "\n";
} else {
q.push(-tmp);
}
}
return 0;
}
Python 코드
import sys, heapq
from collections import deque
input = sys.stdin.readline
li = []
res = deque()
cnt = 0
n = int(input())
for _ in range(n):
x = int(input())
if x:
heapq.heappush(li,x)
else:
cnt += 1
if len(li):
res.append(heapq.heappop(li))
else:
res.append(0)
for i in range(cnt):
print(res.popleft())
회고
오랫만에 백준을 데스크탑으로 풀이했는데, 데스크탑에 C++ 빌드 설정이 안되어있어서 시간을 좀 까먹었다.
처음에 heapq 를 처음 python에서 봤을 때는 이게 뭔지 알아듣지 못해서 그냥 가져다 쓰기만 했었는데, 이제는 알고쓰는게 1년새 실력이늘은것 같기도 하다.
Python 코드를 보면 굉장히 쓸모없는 것들이 많은데, SSAFY 시작하고 입문을 python으로 했다보니 이상한 코드들이 많은 것 같다.
