[코딩테스트] [BOJ1655] 가운데를 말해요

문제

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

---

풀이

1. 중간 값을 top으로 하는 최대 힙(leftQueue)과 중간 값보다 큰 요소들로만 이루어진 최소 힙(rightQueue)을 활용한다.
   ex) [1, 5, 2, 10, -99, 7, 5] 입력을 받았을 때 : 최대 힙 [5, 2, 1, -99] / 최소 힙 [5, 7, 10]

2. leftQueue의 크기는 rightQueue의 크기보다 크거나 같다.
   => 현재 주어진 숫자 개수가 짝수라면, 중간에 있는 두 수 중 작은 값이 중간 값이기 때문이다. 즉, leftQueue의 top이 중간 값이다.

3. 우선 leftQueue에 새로운 입력 값을 넣어주고, 각 우선순위 큐의 크기를 비교하며 균형을 맞춰준다.

---

코드

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

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

    int n = 0;
    cin >> n;

    // 중간값 이하 요소를 내림차순 정렬
    priority_queue<int> leftQueue;

    // 중간값 이상 요소를 오름차순 정렬
    priority_queue<int, vector<int>, greater<int>> rightQueue;

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

        if (leftQueue.empty() || temp <= leftQueue.top())
        {
            leftQueue.push(temp);
        }
        else
        {
            rightQueue.push(temp);
        }

        if (leftQueue.size() > rightQueue.size() + 1)
        {
            rightQueue.push(leftQueue.top());
            leftQueue.pop();
        }
        else if (rightQueue.size() > leftQueue.size())
        {
            leftQueue.push(rightQueue.top());
            rightQueue.pop();
        }

        cout << leftQueue.top() << "\n";
    }

    return 0;
}