개발 지식/알고리즘
[백준] 1927 최소 힙
트리맨스
2021. 6. 30. 00:59
반응형
문제를 읽어보고 오자.
https://www.acmicpc.net/problem/1927
배열에 값을 넣고, 가장 작은 값 부터 pop연산을 하면 된다. 하지만 문제 조건을 보면 최대 10만개의 값이 들어올 수 있으며, 일반적인 배열로 계산하게 되면은 시간 초과가 나게 될 확률이 높다. 여기서 사용해야 할 자료형은 힙 구조 또는 이진 트리 구조를 사용하는 자료구조를 사용하는 것이다.
C++에서는 이러한 구조를 priority_queue 로 구현해 두어서, 사용이 매우 간단하다. 원소를 삽입하는 순간 알아서 정렬이 되게 한다. 지금 다시 힙 또는 이진 트리 구조를 구현하라고 하면, 구현하기 힘들어할 것 같다. 나중에 다시 복습해야겠다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int num, temp; priority_queue<int, vector<int>, greater<int>> q; cin >> num; while (num--) { cin >> temp; if (!temp) { if (!q.size()) cout << "0" << "\n"; else { cout << q.top() << "\n"; q.pop(); } } else q.push(temp); } return (0); } | cs |
반응형