[BaekJoon/백준] 1927번 C++

최대 힙, 최소힙 이러한 용어가 쓰이는

힙정렬 알고리즘에 대한 문제였다.

 

힙

부모의 값이 자식의 값보다 항상 크다 / 또는 작다. => 최대힙/최소힙

힙에서 부모와 자식 관계는 일정하지만, 형제 사이의 대소관계는 일정하지 않다.

 

 

C언어로 힙정렬을 구현했을 때의 코드를 살펴봤는데

진짜 기억이 하나도 안나고...이해도 안되고... 하 ... 쉬고싶다...

 

어느정도 감은 잡았는데, 문제를 구현하는데 있어서 끙끙대다가.. 풀이를 찾아봤다.

 

찾아보니 최소힙 / 최대힙 구현을

C++의 STL인 priority_queue 를 사용하여 구현할 수 있다고 한다.

참고 : twpower.github.io/93-how-to-use-priority_queue-in-cpp

 

 

이를 이용해서 구현해봤다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, temp;
// priority_queue의 기본형. 3개의 인자를 받으며, 마지막 인자가 greater일 경우 최소힙 less인 경우 최대힙이다.
priority_queue<int, vector<int>, greater<int>> q;
int main() {
    
    ios::sync_with_stdio();
    cin.tie(NULL);
    
    
    cin >> N;
    
    while(N--) {

        cin >> temp;
        
        if(temp == 0) {
            if(q.size() == 0)
                cout << "0\n";
            else {
                cout << q.top() << '\n';
            q.pop();
            }
        }
        else {
            q.push(temp);
        }
    }
    
}

정말 간단하게 풀린다..

 

 

오늘은 정말 피곤하다...

힙을 직접 이용해서 풀어볼 시간도 꼭 필요할 것 같다.