백준 2696 중앙값 구하기 (C++)

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

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

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    for (int test = 0; test < t; test++) {

        int n;
        cin >> n;

        vector<int> ans;


        priority_queue<int, vector<int>, greater<int>> pq;


        for (int i = 1; i <= n; i++) {
            int temp;
            cin >> temp;

            pq.push(temp);

            vector<int> arr;

            if (i % 2 == 1) {
                for (int j = 0; j < i / 2; j++) {
                    arr.push_back(pq.top());
                    pq.pop();
                }

                ans.push_back(pq.top());

                for (int j = 0; j < arr.size(); j++) {
                    pq.push(arr[j]);
                }
            }



        }


        cout << ans.size() << "\n";

        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
            if ((i + 1) % 10 == 0) {
                cout << "\n";
            }
        }
        if ((ans.size() + 1) % 10 != 0) {
            cout << "\n";
        }

    }

    return 0;
}

1. 문제

테스트의 개수 t가 주어진다. 각 테스트 케이스에는 수열의 개수 n과 해당 숫자들이 주어진다. 입력이 홀수 개 주어질 때 마다 지금까지 주어진 수열의 중앙값을 구하려 할 때, 그 중앙값의 개수와 각 중앙값들을 출력하라.

2. 풀이

우선순위 큐를 사용하여 풀 수 있다. 우선순위 큐는 값이 들어올 때 마다 이를 적절히 정렬하여 top에 최솟값을 집어넣을 수 있으므로 여기서 중앙값을 찾을 때 까지 뺀 후 중앙값을 저장, 뺀 숫자를 다시 집어넣어서 풀 수 있다.

        for (int i = 1; i <= n; i++) {
            int temp;
            cin >> temp;

            pq.push(temp);

            vector<int> arr;

            if (i % 2 == 1) {
                for (int j = 0; j < i / 2; j++) {
                    arr.push_back(pq.top());
                    pq.pop();
                }

                ans.push_back(pq.top());

                for (int j = 0; j < arr.size(); j++) {
                    pq.push(arr[j]);
                }
            }



        }

우선순위 큐에 값을 입력받을 때 마다 집어넣어준다. 홀수 개의 입력을 받았다면 i/2의 몫 만큼 top의 값을 임시로 저장하고 pop한다. 그렇게 되면 top에 중앙값이 남게 된다. 

 이를 정답 배열에 저장하고 다음 연산을 위해 뺐던 수를 다시 집어넣어준다.

        cout << ans.size() << "\n";

        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
            if ((i + 1) % 10 == 0) {
                cout << "\n";
            }
        }
        if ((ans.size() + 1) % 10 != 0) {
            cout << "\n";
        }

출력 부분이다. 한 줄에는 10개의 수만 입력이 가능하므로 이를 처리해준다. 모든 수 출력이 끝나면 반복문에서 \n 처리가 되지 않았을 경우((ans.size()+1)%10!=0) 처리를 해준다.