[BOJ] 백준 1655 가운데를 말해요

출처: https://www.acmicpc.net/problem/1655

[그래프] 힙(Heap) 자료구조란? 

힙(Heap) 자료구조란?

값이 계속 들어올 때마다 중간값을 출력해주어야 하기 때문에 매번 정렬을 해서 가운데 값을 출력해주면 TLE 발생.

우선순위 큐 사용하여 해결 < 최대 힙(Max heap)과 최소 힙(Min heap) 구조 이용

1. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다.

2. 값을 넣어준 후 최대 힙과 최소 힙의 top 값을 비교해서

   최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.

   이때, 최대 힙의 top값이 중간값이 된다.

   (결과적으로 최소 힙의 값들은 모두 최대 힙보다 큽니다.

 

 

시뮬레이션

입력원소 순서: [1 5 2 10 -99 7 6]

① 원소 1은 max heap에 들어간다.

    - max heap : [1]

    - min heap : [ ]

    ▶ 중간 값 = 1

 

② 원소 5가 들어오면 max heap의 크기가 더 크므로 min heap에 값이 들어간다.

    - max heap : [1]

    - min heap : [5]

    이때, max heap의 top보다 min heap의 top이 크므로 값의 변경은 일어나지 않고,

    ▶ 중간값은 max heap의 top인 1이다.

 

③ 원소 2가 들어오면 크기가 같으므로 max heap에 들어간다.

    - max heap : [1, 2]

    - min heap : [5]

    2는 5보다 작으므로 값의 변경은 일어나지 않는다.

    ▶ max heap의 top인 2가 중간 값이다.

 

④ 원소 10이 들어오면 min heap의 크기가 더 작으므로 min heap에 들어갑니다.

    - max heap : [1, 2]

    - min heap : [5, 10]

    ▶ 중간 값은 max heap의 top값인 2이다.

 

⑤ 원소 -99는 두 heap의 사이즈가 같으므로 max heap에 들어갑니다.

    - max heap : [-99, 1, 2]

    - min heap : [5, 10]

    ▶ 중간 값은 2이다.

 

⑥ 원소 7은 min heap으로 들어갑니다.

    - max heap : [-99, 1, 2]

    - min heap : [5, 7, 10]

    ▶ 중간 값은 그대로 2이다.

 

⑦ 원소 6은 두 heap의 사이즈가 같으므로 max heap에 들어갑니다.

    - max heap : [-99, 1, 2, 6]

    - min heap : [5, 7, 10]

    → maxHeap.top() = 6 > minHeap.top() = 5 이므로 두 값 교환

    - max heap : [-99, 1, 2, 5]

    - min heap : [6, 7, 10]

    ▶ maxHeap.top() = 5가 중간값이 된다.

---

#include <iostream>
#include <queue>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int> > minHeap;
 
    int n, num; 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (maxHeap.size() == minHeap.size())
            maxHeap.push(num);
        else 
            minHeap.push(num);
        
        if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
            // 교환
            int a = maxHeap.top(), b = minHeap.top();
            maxHeap.pop(); minHeap.pop();
            maxHeap.push(b); minHeap.push(a);
        }
        cout << maxHeap.top() << '\n';
    }
}