백준 s2 1927 최소 힙 c++

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

문제

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

기능을 수행하는 최소 힙을 구현하면 된다. 

 

N개의 숫자 x가 들어온다. x가 0이면 최솟값을 출력하고 그 값을 배열에서 제거한다. 그렇지 않으면 x를 큐에 삽입한다.

 

풀이

템플릿은 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x17/heap_test.cpp 이걸 썼다.

 

push 함수

배열 제일 끝 (sz)에 넣고, 부모 (cur/2)와 비교하여 자리를 바꾸면서 root까지 올라간다.

top 함수

큐가 비어있지 않다면 heap[1]을 출력한다.

pop 함수

heap[1] <-> heap[sz]를 바꾸고, root부터 cur, cur*2, cur*2+1끼리 비교해서 최솟값 <-> cur을 바꿔 내려간다.

 

무수한 시간 초과가 났던 이유는 ... 

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

이걸 빼먹음

위 링크의 스켈레톤 코드를 복붙하다가 저 코드를 빼먹었다

 

전체 코드

/*boj s2 1927 최소 힙*/
#include <algorithm>
#include <iostream>

using namespace std;

int heap[100005];
int sz = 0; // heap에 들어있는 원소의 수

void push(int x) {
    heap[++sz] = x;
    int cur = sz;

    while (cur != 1) {
        if (heap[cur / 2] > heap[cur]) {
            swap(heap[cur / 2], heap[cur]);
            cur = cur / 2;
        } else {
            break;
        }
    }
}

int top() {
    if (sz == 0) {
        return 0;
    } else
        return heap[1];
}

void pop() {
    if (sz == 0) {
        return;
    }

    // 1. root <-> 맨 끝
    heap[1] = heap[sz--];
    // 2. root부터 최솟값과 바꾸면서 내려가기
    int cur = 1;
    while (2 * cur <= sz) {
        // 2-1. cur, cur*2, cur*+1 중 최솟값 찾기
        int mn = heap[cur];

        if (cur * 2 <= sz) {
            mn = min(mn, heap[cur * 2]);
        }
        if (cur * 2 + 1 <= sz) {
            mn = min(mn, heap[cur * 2 + 1]);
        }

        if (mn == heap[cur])
            break;
        else if (mn == heap[cur * 2]) {
            swap(heap[cur], heap[cur * 2]);
            cur = cur * 2;
        } else if (mn == heap[cur * 2 + 1]) {
            swap(heap[cur], heap[cur * 2 + 1]);
            cur = cur * 2 + 1;
        }
    }
}

int N;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    int x;
    while (N--) {
        cin >> x;
        if (x == 0) {
            cout << top() << "\n";
            pop();
        } else {
            push(x);
        }
    }
}