1927. 최소 힙

백준 1927번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1927번: 최소 힙

풀이

아이디어

매번 입력이 들어올 때 마다 정렬해서 앞의 것을 제거해주기에는 배열에 들어올 수 있는 입력의 개수가 10만개로 많아서 시간초과가 날 것이다.

그래서 heap 이나 이진트리 구조를 사용하는 자료구조를 사용하는 것이 좋은데… C++에는 다행히 priority_queue로 이 구조를 사용할 수 있게 해 두었다.

따라서 일단은 priority_queue를 이용해서 간단하게 문제를 풀 수 있었다.

아, 입출력에 cin, cout을 사용한다면 priority_queue를 사용했더라도 시간초과가 날 것이다.

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin, cout을 사용했다면 위의 코드를 추가해서 속도를 높여주거나, 아니면 printf, scanf를 사용해야 시간 초과되지 않을 것이다.

코드

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    priority_queue<int, vector<int>, greater<int>> pq;
    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> x;
        if (x == 0){
            if (pq.empty())
                cout << 0 << '\n';
            else{
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else
            pq.push(x);
    }
    return (0);
}