[백준/C++] 11279번 최대 힙

문제링크

11279번 최대 힙

 

간단하게 봤을 때 구현만 친다면 vector를 사용하여 최대값을 구한다음 처리해주는 식으로 구현했지만, 시간제한에 걸리게 됨.

따라서 최대값을 구해줄 때 스택이나 큐와 같이 순차적으로 데이터가 들어온 것을 순회하며
별도의 최대값 구하는 연산을 진행하는 것이 아닌 우선순위가 높은 데이터가 먼저 나가는
우선순위 큐를 사용하여 연산에 수행되는 시간을 줄여 쉽게 풀어줄 수 있음.

우선순위 큐 개념 정리된 위키

우선순위 큐 - 위키백과, 우리 모두의 백과사전

 

 

제출 코드

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N = 0;
    cin >> N;
    vector<int> results;
    priority_queue<int> q;
    for(int i = 0; i < N; i++)
    {
        int x = 0;
        cin >> x;
    
        if(x == 0)
        {
            if(!q.empty())
            {
                results.push_back(q.top());
                q.pop();
            }
            else
            {
                results.push_back(0);
            }
        }
        else
        {
            q.push(x);
        }
    }

    for(int i = 0; i < results.size(); i++)
    {
        cout << results[i] << "\n";
    }

    return 0;
}