[c++] 1655 가운데를 말해요 (힙!)

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

1655번: 가운데를 말해요

 

짭 중간값 구하는 문제 !

시간 제한이 0.1초에 데이터의 삽입이 끊임없이 이뤄지므로 수행속도가 빠른 heap을 사용한다 

 

max heap : 가장 큰 값이 top (기준 값보다 작은 값들을 나열, 기준 값 포함)

기준 값 !

min heap : 가장 작은 값이 top (기준 값보다 큰 값들을 나열, 기준 값 제외)

 

해서 중간값이 max heap 의 top에 위치하도록 한다.

= max heap 의 사이즈가 min heap 과 같거나 하나 크다.

 

짝수개 있을 땐 중간값 두개 중에 작은 값을 출력하라고 했으니 max heap 의 top 에 위치하도록 한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int N, num;
priority_queue<int> small;  // max heap
priority_queue<int, vector<int>, greater<int>> big; // min heap

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    cin >> num;
    small.push(num);
    cout << num << "\n";
    N--;
    while (N--) {
        cin >> num;
        if (num < small.top()) {
            small.push(num);
        }
        else {
            big.push(num);
        }
        
        if ((int)small.size() < (int)big.size()) {
            small.push(big.top());
            big.pop();
        }
        else if ((int)small.size() > (int)big.size() + 1) {
            big.push(small.top());
            small.pop();
        }
        
        cout << small.top() << "\n";
    }
    
    return 0;
}