백준 1655 가운데를 말해요 (C++)

1655번: 가운데를 말해요

우선 순위 큐를 이용하여 풀 수 있는 문제이다. 문제를 보면 주어지는 입력마다 정렬을 하여 가운데에 해당하는 수를 출력해주어야 한다. 그리고 제한 시간도 0.5초밖에 되지 않기에 힙 정렬을 사용하는 우선 순위 큐를 사용해주어야 한다. 큐는 오직 top에만 접근이 가능하기에 두개의 큐로 나누어 가운데 값에 접근해주었다. pq1은 내림차순, pq2는 오른차순으로 두고 첫번째 값은 pq1에 넣어두고 이 값보다 작으면 pq1, 크면 pq2에 저장하였다. 가운데 값을 출력해야하기 때문에 두 큐의 크기를 비교하여 2 이상으로 차이가 날 경우 큰 쪽에서 작은 쪽으로 top에 해당하는 값을 옮겨주고 크기가 크거나 같은 큐의 top을 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.
처음에는 이전에 문제를 풀면서 알게된 multiset을 사용해보려고 했으나 값을 옮기는 과정이 큐에 알맞기때문에 우선 순위 큐로 바꿔 다시 풀었었다. 골드 2 문제도 생각보다 쉽게 풀려 자신감이 좀 상승했다. 상위 난이도 문제들도 많이 풀어봐야 겠다.

#include <iostream>
#include <queue>

using namespace std;

int N;
int A[100000];
priority_queue<int> pq1;
priority_queue<int, vector<int>, greater<int>> pq2;

void solution() {
    pq1.push(A[0]);
    cout << pq1.top() << "\n";

    for (int i = 1; i < N; i++) {
        if (pq1.top() > A[i]) pq1.push(A[i]);
        else pq2.push(A[i]);

        if (pq1.size() > pq2.size() + 1) {
            int tmp = pq1.top();
            pq1.pop();
            pq2.push(tmp);
        }
        else if (pq2.size() > pq1.size() + 1) {
            int tmp = pq2.top();
            pq2.pop();
            pq1.push(tmp);
        }

        if (pq1.size() >= pq2.size()) {
            cout << pq1.top() << "\n";
        }
        else {
            cout << pq2.top() << "\n";
        }
    }
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}