BOJ 11279 최대 힙

개요

BOJ 11279 최대 힙

• 백준 온라인 저지 11279번 문제
• BOJ 28단계

C++

배열 사용

#include <iostream>
using namespace std;

int A[100001];
int len = 0;

int pop() {
    if(len < 1) {
        return 0;
    }
    len--;
    return A[len];
}

int search(int x) {
    int start = 0;
    int end = len;
    int mid = 0;
    while(start < end) {
        mid = (start+end)/2;
        if(A[mid] < x) {
            mid++;
            start = mid;
        } else {
            end = mid;
        }
    }
    return mid;
}

void push(int x) {
    int idx = search(x);
    for(int i=len; i>idx; i--) {
        A[i] = A[i-1];
    }
    A[idx] = x;
    len++;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, x;
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> x;
        if(x == 0) {
            cout << pop() << '\n';
        } else {
            push(x);
        }
    }
}

priority_queue 사용

#include <iostream>
#include <queue>
using namespace std;
 
priority_queue<int> q;

int pop() {
    if(q.empty()) {
        return 0;
    }
    int temp = q.top();
    q.pop();
    return temp;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, x;
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> x;
        if(x == 0) {
            cout << pop() << '\n';
        } else {
            q.push(x);
        }
    }
}