가운데를 말해요 - 1655

//1655 - 가운데를 말해요
 
#include <iostream>
#include <queue>
using namespace std;
 
int N;
priority_queue<int> hq, tq;
 
void init()
{
    hq = tq = priority_queue<int>();
    cin >> N;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int x;
    int ht, tt, hsize, tsize;
    cin >> x, hq.push(x);
    cout << x << "\n";
    for(int i = 1; i<N; ++i)
    {
        cin >> x;
        if(hq.size() > tq.size())
        {
            if(hq.top() <= x)
                tq.push(-x);
            else
            {
                tq.push(-hq.top());
                hq.pop();
                hq.push(x);
            }
            
        }
        else
        {
            if(-tq.top() >= x)
                hq.push(x);
            else
            {
                hq.push(-tq.top());
                tq.pop();
                tq.push(-x);
            }
        }
        cout << hq.top() << "\n";
    }
}

 

 

 

 

 

 

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

1655번: 가운데를 말해요

 

 

 

 

 

 

가운데를 말해요

우선순위큐를 두개 만들었습니다.

하나는 숫자가 큰것이 우선순위가 높게 설정했고,  --> hq

하나는 숫자가 작은것을 우선순위가 높게 설정했습니다. --> tq

hq의 원소의 개수는 tq와 같거나 하나 많은 경우만 가능하고, hq에는 비교적 작은얘들, tq에는 큰 얘들이 들어가게 유지했습니다.