[C++] 백준 11279 - 최대 힙(우선순위 큐, 힙)

0. [c++] 백준

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

1. 풀이

이 문제를 풀기 위해서 priority_queue를 활용하면 귀찮게 함수를 선언하지 않고 힙을 활용할 수 있지만, 이번에는 직접 heap을 구현해보았다.

1. heap의 특성

힙을 구현하기 위해서 우선 힙의 특성을 알아보자.

우선 힙은 시작 주소를 1로 가진다.

또한, 힙을 int arr[50]이라 구현하였다 가정하면, i번째 원소 arr[i]의 부모는 arr[i/2]이다.

arr[i]의 자식 노드는 arr[i*2], arr[i*2+1]을 갖는 특성을 가지고 있다.

이러한 특성을 유지시키면서 push와 pop의 기능을 가지도록 해주어야하는데, 이걸 유지하기 위해서 push부터 확인해보자.

1. push 구현

push를 구현하기 위한 포인트는 항상 마지막에 원소를 추가하고, 자신과 부모노드의 비교를 통해 더 큰 값이 부모노드가 되도록 변경해준다. 변경이 되지 않는 지점이거나 root가 될 때 까지 반복을 해주면 된다.

예를 들어보자. arr[50]이라는 배열에 1~3에는 9, 6, 5 라는 숫자가 저장되어있다.

이때, push(7)이라는 입력이 들어오면

1) arr[4] = 7이 저장된다.

2) arr[2] < arr[4]이다. 그러므로 arr[2]와 arr[4]의 값이 변경되게 된다. 즉 arr[2] = 7, arr[4] = 6이 된다.

3) arr[1] > arr[2]이다. 그러므로 변경이 되지 않고, 반복이 종료되게 된다.

2. pop 구현

pop은 arr[1]을 출력하고, 가장 마지막 원소를 arr[1]에 넣어주고 순차적으로 자식 노드와 변경을 통해 구현이 이루어지게 된다.

pop과 거의 비슷하다고 생각하면 된다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include<iostream>   using namespace std;   int N;   int heap[100050]; int pointer = 0;   void push(int num) {     heap[++pointer] = num;     int iter = pointer;     int temp;     while (iter > 1) {         if (heap[iter] > heap[iter / 2]) {             temp = heap[iter];             heap[iter] = heap[iter / 2];             heap[iter / 2] = temp;         }         else             break;         iter /= 2;     } }   void pop() {     if (pointer > 0) {         cout << heap[1] << "\n";         heap[1] = heap[pointer--];         int iter = 1, temp;         int flag = 0;         while (iter < pointer) {             flag = 0;             if (heap[iter] < heap[iter * 2] && iter * 2 <= pointer) {                 flag = 1;                 if (heap[iter * 2] < heap[iter * 2 + 1] && iter * 2 + 1 <= pointer) {                     flag = 2;                 }             }             else if (heap[iter] < heap[iter * 2 + 1] && iter * 2 + 1 <= pointer) {                 flag = 2;             }             if (flag == 0)                 break;             else if (flag == 1) {                 iter *= 2;                 temp = heap[iter];                 heap[iter] = heap[iter / 2];                 heap[iter / 2] = temp;             }             else {                 iter = iter * 2 + 1;                 temp = heap[iter];                 heap[iter] = heap[iter / 2];                 heap[iter / 2] = temp;             }         }     }     else {         cout << 0 << "\n";     } }   int main() {     cin.tie(0);     cin.sync_with_stdio(0);     cin >> N;     int temp;     for (int i = 0;i < N;i++) {         cin >> temp;         if (temp == 0) {             pop();         }         else {             push(temp);         }     } } Colored by Color Scripter

cs

- 우선순위 큐 활용

#include <iostream>
#include <queue>
 
using namespace std;
 
int N;
 
int main(void)
{
    cin.sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
 
    priority_queue<int> pq;
 
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        if (num == 0)
        {
            if (pq.empty())
                cout << 0 << "\n";
            else {
                cout << pq.top() << "\n";
                pq.pop();
            }
        }
        else
            pq.push(num);
    }
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!