[백준] 2696번: 중앙값 구하기

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

2696번: 중앙값 구하기

파이썬에서는 최대힙과 최소힙을 함수로 만들어야해서 너무 귀찮았다.

그래서 이번에는 c++로 코드를 짜보았다.

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

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

    int M, x, TC, medianCnt;
    cin >> TC;
    while(TC--) {
        priority_queue<int> maxHeap;
        priority_queue<int, vector<int>, greater<int>> minHeap;

        cin >> M; // 문제조건 M = 홀수
        cout << M / 2 + 1 << '\n';

        medianCnt = 0; // 한 줄에 10개씩 출력하기 위함
        for (int i = 1; i <= M; i++) {
            cin >> x;
            if (maxHeap.size() == minHeap.size())
                maxHeap.push(x);
            else
                minHeap.push(x);
            if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
                int a = maxHeap.top(); maxHeap.pop();
                int b = minHeap.top(); minHeap.pop();

                minHeap.push(a); maxHeap.push(b); // 스왑
            }

            // 홀수 번째 수인 경우
            if (i % 2) {
                cout << maxHeap.top() << ' ';
                medianCnt++;
                // 10개씩 1줄단위 처리
                if (medianCnt % 10 == 0)
                    cout << '\n';
            }
        }
        cout << '\n';
    }
}

https://zoosso.tistory.com/503

[BOJ] 백준 2696 중앙값 구하기