BOJ 11279 - 최대힙, BOJ 1927 - 최소힙

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

11279번: 최대 힙

 

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

1927번: 최소 힙

 

둘은 구현 방식에 있어서 큰 차이가 있는 문제가 아니기 때문에 하나로 묶었다.

 

처음에는 아래 처럼 힙을 클래스를 사용해서 직접 구현하려 했다.

 

- c++

#include <iostream>
#define MAX 100001
 
using namespace std;
 
int N;
 
class MinHeap {
   private:
    int arr[MAX];
    int size;
 
   public:
    MinHeap();
    void swap(int* a, int* b);
    void insert(int x);
    void delete_data();
    int arr_size();
};
 
MinHeap::MinHeap() {
    this->size = 0;
}
 
void MinHeap::swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = *a;
}
 
void MinHeap::insert(int x) {
    int here = ++this->size;
 
    while ((here != 1) && x < this->arr[here / 2]) {
        this->arr[here] = this->arr[here / 2];
        here /= 2;
    }
    this->arr[here] = x;
}
 
void MinHeap::delete_data() {
    if (this->size == 0) return;
    int root_node = this->arr[1];
    this->arr[1] = this->arr[this->size--];
 
    int parent = 1;
    int child;
 
    while (1) {
        child = parent * 2;
        if (child + 1 <= this->size && this->arr[child] > this->arr[child + 1])
            child++;
 
        if (child > this->size || this->arr[child] > this->arr[parent])
            break;
 
        this->swap(&this->arr[parent], &this->arr[child]);
        parent = child;
    }
 
    cout << root_node << '\n';
    return;
}
 
int MinHeap::arr_size() {
    return this->size;
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> N;
 
    MinHeap mh;
 
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
 
        if (x == 0) {
            if (!(mh.arr_size())) {
                cout << 0 << '\n';
            } else {
                mh.delete_data();
            }
        } else if(x > 0) {
            mh.insert(x);
        }
    }
 
    return 0;
}

 

 

 

이렇게 풀다 보면 코드도 길뿐더러, 통과도 하지 못했다.

 

그러다가 다른 사람이 푼것을 봤는데,

출처 : https://jaimemin.tistory.com/1005

백준 1927번 최소 힙

 

이런 유형은 이렇게 STL 을 이용해서 빠르게 풀어야 되는것임을 느끼게 되었다.

아래는 최대 힙에 대한 코드다 (최소힙은 less<int> 를 greater<int> 로 바꾸면 된다)

- c++

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int N;
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
 
    priority_queue<int, vector<int>, less<int>> pq;
 
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
 
        if (!(x) && pq.empty()) {
            cout << 0 << '\n';
        } else if (!(x)) {
            cout << pq.top() << '\n';
            pq.pop();
        } else {
            pq.push(x);
        }
    }
 
    return 0;
}

 

 

 

 

PS 를 하다 보면

뭔가 마치 수능 보듯

유형별 풀이법을 외우면서 푸는것 같다

원래 이런건가? 라는 생각이 든다