가운데를 말해요 1655

문제

접근 방법

우선순위 큐를 사용하면 된다고 생각했다.
두 큐의 크기와 가운데 값을 생각하여서 조절해주면 된다.

1

예제대로 실행해보자. 처음은 1이다.

1	5

짝수이기에 더 작은 값인 1을 출력한다.

2	5
1

1보다 크고 5보다 작은 2를 출력한다.

2	5
1	10

짝수이기에 2를 출력한다.

2	5
1	10
-99

2를 출력한다.

2	5
1	10
-99	7

2를 출력한다.

5	5
2	10
1	7
-99

5를 출력한다.
기존 값보다 낮은 값만 계속 줄 수도 있고 큰 값만 계속 줄 수도 있기에 균형을 맞추면서 해결해줘야 한다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue<int> hpq;
    priority_queue<int, vector<int>, greater<int>> lpq;
    int N;
    cin >> N;
    while (N--)
    {
        int num;
        cin >> num;
        if (hpq.empty() || hpq.top() > num)
        {
            hpq.push(num);
        }
        else
        {
            lpq.push(num);
        }
        if (lpq.size() > hpq.size())
        {
            hpq.push(lpq.top());
            lpq.pop();
        }
        else if (hpq.size() > lpq.size() + 1)
        {
            lpq.push(hpq.top());
            hpq.pop();
        }
        cout << hpq.top() << "\n";
    }
    return 0;
}

풀이

작은 것의 큰 값, 큰 것의 작은 값이 중간값이라는 것을 생각하면 풀 수 있다.