[BOJ] 백준 2696 중앙값 구하기

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

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

힙(Heap) 자료구조란?

우선순위 큐 이용 (C++ STL priority_queue는 내부적으로 Heap 구조로 이루어져 있음)

- 우선순위큐를 2개 준비 (최대 힙과 최소 힙)

- 새로운 원소가 들어올 때 다음의 과정 수행

① 두 개의 큐에 쌓인 원소의 개수 비교

    - 같으면 maxHeap에 push

    - 다르면 minHeap에 push

    결과적으로 maxHeap의 원소 개수는 minHeap의 개수와 같거나 한 개 더 많다.

② 두 개의 큐가 비워지지 않은 경우, maxHeap과 minHeap의 top() 값과 비교

    minHeap.top() < maxHeap.top()이며, 두 top()의 위치를 바꿔줍니다.

 

시뮬레이션

입력 원소: [1 2 3 4 5 6 7 8 9]

▶ 원소의 개수는 9(=M) 출력한 중앙값의 개수는 9 / 2 + 1 = 5개 출력

 

1 push

maxheap = [1] 

minheap = []

 

2 push

maxheap = [1] 

minheap = [2]

 

3 push

maxheap = [1 3]

minheap = [2]

→ minHeap.top() < maxHeap.top()이므로 top() 값을 swap

maxheap = [1 2]

minheap = [3]

 

4 push

maxheap = [1 2]

minheap = [4 3]

 

5 push

maxheap = [1 2 5]

minheap = [4 3]

→ minHeap.top() < maxHeap.top()이므로 top() 값을 swap

maxheap = [1 2 3]

minheap = [5 4]

 

6 push

maxheap = [1 2 3]

minheap = [6 5 4]

 

7 push

maxheap = [1 2 3 7]

minheap = [6 5 4]

→ minHeap.top() < maxHeap.top()이므로 top() 값을 swap

maxheap = [1 2 3 4]

minheap = [7 6 5]

 

8 push

maxheap = [1 2 3 4]

minheap = [8 7 6 5]

 

9 push

maxheap = [1 2 3 4 9]

minheap = [8 7 6 5]

→ minHeap.top() < maxHeap.top()이므로 top() 값을 swap

maxheap = [1 2 3 4 5]

minheap = [9 8 7 6]

---

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int M, x, TC, medianCnt;
    cin >> TC;
    while (TC--) {
        priority_queue<int> maxHeap;
        priority_queue<int, vector<int>, greater<int> > minHeap;
 
        cin >> M; // (문제조건) M = 홀수
        cout << M / 2 + 1 << '\n';
 
        medianCnt = 0; // 한 줄에 10개씩 출력하기 위함.
        for (int i = 1; i <= M; i++) {
            cin >> x;
            if (maxHeap.size() == minHeap.size())
                maxHeap.push(x);
            else
                minHeap.push(x);
 
            if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
                int a = maxHeap.top(); maxHeap.pop();
                int b = minHeap.top(); minHeap.pop();
                
                minHeap.push(a); maxHeap.push(b);
            }
 
            // 홀수 번째 수인 경우
            if (i % 2) {
                cout << maxHeap.top() << ' ';
                medianCnt++;
                // 10개씩 1줄단위 처리
                if (medianCnt % 10 == 0)
                    cout << '\n';
            }
        }
        cout << '\n';
    }
}