백준/1655번/가운데를 말해요/골드2

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

문제 설명

Site: Baekjoon
Number: 1655
Category: 우선순위 큐
Rank: Gold 2

지속적으로 주어지는 숫자들 중 중간값을 출력하는 문제입니다.

숫자가 주어질 때 마다 정렬하여 중간값을 출력한다면 시간초과가 발생하기 때문에 다른 방식으로 풀어야합니다.

우선순위 큐 두 개를 사용하여 중간값을 구하는 방식을 사용해서 풀었습니다.

하나의 우선순위 큐는 내림차순, 다른 하나의 우선순위 큐는 오름차순으로 정렬하여 사용합니다.

풀이방법

1. 첫 원소는 내림차순 큐에 삽입합니다.
2. 원소가 들어올때 마다 양쪽 큐의 갯수가 같다면 내림차순 큐에, 다르다면 오름차순 큐에 원소를 삽입합니다.
3. 원소 삽입 후 내림차순 큐의 첫 원소가 오름차순 큐의 첫 원소보다 크다면 두 첫 원소를 교체합니다.
4. 2번과 3번을 지속적으로 반복할 때 마다 내림차순의 첫 원소가 중간값이 됩니다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N;
    cin >> N;

    //오름차순 큐
    priority_queue<int, vector<int>, greater<>> pq_min;

    //내림차순 큐
    priority_queue<int, vector<int>, less<>> pq_max;

    int num;
    cin >> num;

    //첫 원소 삽입
    pq_max.emplace(num);
    cout << pq_max.top() << '\n';

    for(int i = 1; i < N; i++)
    {
        cin >> num;

        //원소의 갯수에 따라 내림차순 큐 또는 오름차순 큐에 삽입
        if (pq_max.size() == pq_min.size())
            pq_max.emplace(num);
        else
            pq_min.emplace(num);

        //원소 교체
        if(pq_max.top() > pq_min.top())
        {
            int a = pq_max.top();
            pq_max.pop();
            int b = pq_min.top();
            pq_min.pop();

            pq_max.emplace(b);
            pq_min.emplace(a);
        }

        cout << pq_max.top() << '\n';
    }

    return 0;
}