알고리즘/백준

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

KANTAM 2024. 3. 7. 21:02

문제

 

2696번: 중앙값 구하기

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주

www.acmicpc.net

풀이

우선순위 큐

 

 

[백준][C++] 1655: 가운데를 말해요

문제 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가

kantatatam.tistory.com

위의 문제와 풀이가 같다. 들어오는 수를 저장해 두고, 홀수번마다 현재 중앙값을 출력한다. 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

priority_queue<int> smaller;
priority_queue<int, vector<int>, greater<int>> bigger;
vector<int> nums;

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

    int T;
    cin >> T;

    while (T--)
    {
        int M;
        cin >> M;

        while (!smaller.empty())
        {
            smaller.pop();
        }
        while (!bigger.empty())
        {
            bigger.pop();
        }
        nums.clear();

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

            nums.push_back(num);
        }

        if (nums.size() % 2 == 1)
        {
            cout << (nums.size() / 2) + 1;
        }
        else
        {
            cout << nums.size() / 2;
        }
        cout << '\n';

        for (int i = 1; i <= M; ++i)
        {
            int num = nums[i - 1];

            if (smaller.empty())
            {
                smaller.push(num);
            }
            else if (smaller.size() == bigger.size())
            {
                smaller.push(num);
            }
            else
            {
                bigger.push(num);
            }

            if (!smaller.empty() && !bigger.empty() && smaller.top() > bigger.top())
            {
                int a = smaller.top();
                smaller.pop();
                int b = bigger.top();
                bigger.pop();

                bigger.push(a);
                smaller.push(b);
            }

            if (i % 2 == 1)
            {
                cout << smaller.top() << " ";
            }
            if (i % 20 == 0)
            {
                cout << '\n';
            }
        }

        cout << '\n';
    }

    return 0;
}