[백준 11279] 최대 힙

최대 힙

문제설명

첫 줄에 연산의 수를 입력하고, 연산의 수만큼 매 줄마다 정수 x가 입력된다.
0이 입력되면 배열안의 가장 큰 수를 출력하고 지운다.

자연수가 입력되면 배열안에 값을 넣는다.
따라서 0이 나올때 마다 그 결과 값을 출력하면 된다. 만약 배열이 빈 경우 0이 입력되면 0을 출력한다.

---

알고리즘

1. 연산의 수를 입력 받고 priority_queue를 선언한다.
2. 0이 입력 될 때마다 비어있으면 0, 그렇지 않으면 top을 출력하고 pop해준다.
3. 그 외의 자연수가 입력되면 push해준다.

---

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;    // 사람수 입력    
    priority_queue<int> p;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;

        if (num == 0)//0이 입력된 경우
        {
            if (p.empty() == true)//비어있을 때
                cout << 0 << "\n";
            else//비어있지 않은 경우
            {
                cout << p.top() << "\n";//값 출력
                p.pop();//값 지우기
            }
        }
        else//값 넣기
            p.push(num);
    }

    return 0;
}

고찰

이번 문제는 priority queue를 사용하면 간단하게 풀 수 있는 문제이다.
priority queue의 경우 값이 들어오면 자연스럽게 맨위를 가장 큰 값으로 만들어주는 queue이다.