(11286) 절댓값 힙

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

단계별로 풀어보기

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

 

 

 

일반적으로 람다 함수는 우선순위 큐의 비교 함수로 넣을 수 없지만, 이렇게 하면 사용할 수 있다.

람다식의 자료형을 비교 함수 자리에 템플릿 매개 변수로 넘겨야 하는데, function으로 명시적으로 지정하거나 decltype을 사용하면 된다. 자세히 찾아보면 굉장히 복잡하지만, 간단히 decltype은 인자의 타입을 반환한다고 생각하면 된다.

또한 람다식의 자료형을 알아도 괄호 연산자의 결과가 자동으로 정의되지 않으므로 람다식을 생성자로 직접 넘겨야 한다.

 

또한 우선순위 큐의 비교 함수에 대해 헷갈리는 경우가 많은데, 배열/벡터의 맨 끝 원소를 먼저 꺼낸다고 생각하면 된다. 그래서 정렬의 비교 함수와 직관적으로 반대인 것처럼 느껴지는 것이다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  auto cmp= [](int A, int B){
    if(abs(A)!=abs(B))  return abs(A)>abs(B);
    return A>B;
  };
  priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
  
  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;
}