본문 바로가기
알고리즘

[백준 1927] 알고리즘 96일차 : 최소 힙

by SiO2whocode 2021. 6. 30.
반응형

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

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

우선순위 큐

최소 힙이라 비교로직만 바꿔주면 된다.

less<> 대신 greater<>로

이번엔 greater<>자리에 비교연산만 구현해서 넣어봤다. 오름차순이라 a < b 로 하면 될줄 알았는데 a > b 였다..

 

소스코드

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

struct cmp{
    bool operator()(int a, int b){
        return a > b; //주의 greater
    }
};


int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    priority_queue<int, vector<int>, cmp> heap;
//    priority_queue<int, vector<int>, greater<>> heap;

    int t;
    cin >> t;
    
    int x;
    for(int i = 0 ; i < t ; i++){
        cin >> x;
        if(x == 0){
            if(heap.empty()){
                cout << "0\n";
            }else{
                cout << heap.top() << "\n";
                heap.pop();
            }
        }else{
            heap.push(x);
        }
    }
    
}
반응형

댓글0