(1927) 최소 힙

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

단계별로 풀어보기

26단계(우선순위 큐) 2번째

 

 

 

우선순위 큐의 인자는 Type(자료형), Container(컨테이너), Compare(비교 함수)로 세 개가 있다. 컨테이너의 기본값은 vector, 비교 함수의 기본값은 less(최대 힙)이여서 생략하고 자료형만 정해주고 선언할 수 있다.

만약 최소 힙을 선언하고 싶다면 비교 함수를 greater로 선언하면 된다. 부호를 바꾸고 저장하라거나 하는 꼼수도 있는데, 문제에 따라 통하지 않을 수도 있으니 정석적으로 최소 힙을 선언하는게 좋다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  priority_queue<int, vector<int>, greater<int>> pq;
  
  while(n--){
    int t;
    
    cin >> t;
    
    if(t){
      pq.push(t);
    }else{
      if(!pq.empty()){
        cout << pq.top() << "\n";
        pq.pop();
      }else{
        cout << "0\n";
      }
    }
  }
  
  return 0;
}