BOJ 1655. 가운데를 말해요

BOJ 1655. 가운데를 말해요

랭크 : 골드2

문제 풀이

우선 순위 큐를 두 개 만드는데 하나는 큰 값들이 오름차순으로, 하나는 작은 값들을 내림차순으로 만들어서 두 개의 큐가 계속 크기가 1개 이상 차이나지 않도록 유지하면 작은 값들의 Top이 답이 됩니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, tmp;
priority_queue<int> pqlow;
priority_queue<int, vector<int>, greater<int>> pqup;

int main() {
    fastio;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        if (pqlow.size() == pqup.size()) {
            if (!pqup.empty() && tmp >= pqup.top()) {
                pqlow.push(pqup.top()); pqup.pop();
                pqup.push(tmp);
            } else pqlow.push(tmp);
        } else {
            if (!pqlow.empty() && tmp <= pqlow.top()) {
                pqup.push(pqlow.top()); pqlow.pop();
                pqlow.push(tmp);
            } else pqup.push(tmp);
        }
        cout << pqlow.top() << "\n";
    }
}

알고리즘	시간복잡도	공간복잡도
priority_queue	$O(N log N)$	$O(N)$