문제

설명

보자마자 에디터 문제의 아이디어가 떠올랐다.
얘는 우선순위 큐로 커서를 유지하면 되겠구나.
왼쪽은 max heap, 우측은 min heap으로 만들어
가운데 값을 항상 쓸 수 있게 유지하려는 전략을 세웠다.

짝수 원소 개수의 경우에는 left.size() == right.size(),
홀수 원소 개수의 경우에는 left.size() == right.size() + 1
로 유지하는 것이 관건이다.
이렇게 해야 left.top()을 했을 때 가운데 값에 즉시 접근할 수 있다.

left/right 가 비어있을 때

• left가 빈 경우
  비교 대상이 없다. 따라서 그냥 왼쪽에 집어넣는다.
• right가 빈 경우
  왼쪽에 비교대상이 있다. 왼쪽보다 작으면 left.top()을 오른쪽으로 옮기고
  원소는 왼쪽에 넣는다.

left/right에 원소가 있을 때

이제부터는 한 가지 원칙에만 따르면 된다.
1. left.top()보다 크거나 같으면 오른쪽에, 작으면 왼쪽에 넣는다.
2. 짝수 원소 개수의 경우에는 left.size() == right.size(),
홀수 원소 개수의 경우에는 left.size() == right.size() + 1
을 유지한다.

코드

// 2022.02.26 16:27:26
// 1655 https://boj.kr/1655
#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    priority_queue<int> l;
    priority_queue<int, vector<int>, greater<int>> r;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;

        if (l.size() && r.size())
        {
            if (l.top() <= tmp)
            {
                r.push(tmp);
            }
            else
            {
                l.push(tmp);
            }
            while (l.size() > r.size())
            {
                r.push(l.top());
                l.pop();
            }
            while (l.size() < r.size())
            {
                l.push(r.top());
                r.pop();
            }
        }
        else
        {
            if (l.size())
            {
                if(l.top() > tmp)
                {
                    r.push(l.top());
                    l.pop();
                    l.push(tmp);
                }
                else{
                    r.push(tmp);
                }
            }
            else
            {
                l.push(tmp);
            }
        }
        cout << l.top() << "\n";
    }
}