[백준] 1927번 최소 힙 (C++)

문제

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

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

입력

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

예제 입력 1

9
0
12345678
1
2
0
0
0
0
32

출력

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

예제 출력 1

0
1
2
12345678
0

풀이

문제 해결 방법

이 문제는 최소 힙을 구현하거나 STL의 우선순위 큐를 사용하여 해결할 수 있습니다. 두 가지 방법으로 구현해보겠습니다:

1. 직접 구현 방식: 배열을 사용하여 최소 힙을 직접 구현
2. STL 사용 방식: C++ STL의 priority_queue를 사용

두 방법 모두 시간 복잡도는 삽입과 삭제 연산에 대해 O(log N)입니다.

코드

직접 구현 방식

#include <stdio.h>

int n;
int heap[263000];
int hsize;

int main()
{
    int i;
    scanf("%d", &n);
    int x;
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        if (x == 0) // heap 에서 삭제
        {
            int output = heap[1];

            heap[1] = heap[hsize--];
            int node = 1;
            while (node <= hsize)
            {
                    //index 체크 필수!
                int lnode = node * 2;
                int rnode = node * 2 + 1;
                if (heap[lnode] < heap[node] && heap[lnode] <= heap[rnode])
                {
                    swap(heap[lnode], heap[node]);
                    node = lnode;
                }
                else if (heap[rnode] < heap[node] && heap[rnode] < heap[lnode])
                {
                    swap(heap[rnode], heap[node]);
                    node = rnode;
                }
                else break;
            }
        }
        else // heap 에 x를 추가
        {
            heap[++hsize] = x;
            int node = hsize;
            while (node != 1 && heap[node] < heap[node / 2])
            {
                swap(heap[node], heap[node / 2]);
                node /= 2;
            }
        }
    }
    return 0;
}

STL을 이용한 구현

#include <queue>
#include <vector>
#include <stdio.h>
#include <functional>

using namespace std;

struct compare
{
    bool operator()(const int &a, const int &b) {
        return a > b;
    }
};
typedef pair<int, int> pii;
pair<int, int> p;
int n;
priority_queue<int, vector<int>, compare> q;
// 기본 max heap
// priority_queue<int> q;
// 기본 min heap
 priority_queue<pii, vector<pii>, greater<pii> > q;

int main()
{
    p.first;
    p.second;
    p = { 1,2 };
    int i;
    scanf("%d", &n);
    int x;
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        if (x == 0) // heap 에서 삭제
        {
            if (q.empty())
            {
                printf("0\n");
            }
            else {
                int out = q.top(); q.pop();
                printf("%d\n", out);
            }
        }
        else // heap 에 x를 추가
        {
            q.push(x);
        }
    }
    return 0;
}