![[1927번] 최소 힙](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbLrZYV%2FbtqwYTBFbhP%2FRlbwPVmkIKRen7imWhuSdk%2Fimg.png)
반응형
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.
www.acmicpc.net
이전 포스팅했던 글과 매우 유사합니다.
[여기]를 참고하여 Heap(또는 priority_queue)를 이해하고 거의 같은 문제라는 것을 보시기 바랍니다.
이번에는 min Heap을 구현하여 맞는 opration들을 수행해주면 됩니다.
priority_queue Container를 이용하면 되지만 이전에 보여드렸던 MAX Heap과는 달리 좀 더 많은 인자들을 넣어주어야 합니다.
ex) priority_queue<int> → MAX Heap
priority_queue<int, vector<int>, greater<int> > → min Heap
이제 문제를 풀어봅시다!
반응형