BOJ 11279 - 최대 힙 문제풀이

문제를 읽고 이해하기

널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

 

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

 

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

재정의와 추상화

전형적인 우선순위 큐(priority_queue, 이하 pq)를 이용한 최대 힙 문제인데, x가 0일 경우 pq.top()을 출력하고 pq.pop()을 통해 최상단의 값을 제거한다. 단, pq.empty()가 true(pq가 비어있음)일 경우, 0을 출력한다. 이 작업을 N번 반복한다.

 

왜 최상단에 최댓값이 들어는지는 C++ STL priority_queue에 대해 학습한 후 문제를 풀기 바란다!

 

여담이지만, 2^31(2147483648)과 같은 수를 문제에서 준다면, 이는 int값의 범위를 암시하는 것으로, 이 문제에서는 int형 배열을 사용하라는 의미로 해석될 수 있다.

 

* BOJ 1927 - 최소 힙 문제에서 priority_queue 객체의 선언 방식만 바꾸면 바로 풀 수 있는 문제이다. priority_queue 객체 선언 시 

priority_queue<int, vector<int>, less<int>> pq;

위와 같이 세 번째 매개변수에 less<int>를 명시해줘도 되지만, 디폴트로 priority_queue는 내림차순이므로 생략해도 된다.

 

> C++ STL priority_queue

 

코드 작성

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

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue<int, vector<int>> pq;
    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;

        if (x) {
            pq.push(x);
        } else {
            if (!pq.empty()) {
                cout << pq.top() << '\n';
                pq.pop();
            } else
                cout << 0 << '\n';
        }
    }
    return 0;
}

 

짚고 넘어가기

이 문제에서 아래와 같은 코드를 입력하지 않으면, 시간 초과가 발생한다.

cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이 코드들은 iostream의 std::cin, std::cout을 사용할 때 연산 시간을 줄여주는 장치로, cin과 cout을 사용해야 한다면 웬만하면 위 3줄을 꼭 쓰고 시작하자. 특히 이번 문제처럼 입출력이 많을 때는 반드시 써줘야 한다.

 

유사 문제

BOJ 1927 - 최소 힙 문제풀이