2696. 중앙값 구하기

문제

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1<=M<=9999, M=홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다. (대부분의 언어에서 int)

출력

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

 

시간 안에 어떻게 할지 몰라서 솔직히 커닝했다.. ㅋㅋ

그래도 어떻게 하는지 알고리즘을 알았다.

 

기본은 우선순위큐를 2개 이용하면 된다.

기본적으로 우선순위큐가 Heap 구조이므로

MaxHeap, MinHeap 두개를 선언한다

 

우선 첫 출력은 그냥 n/2+1이다. 홀수개니 ㅎㅎ;

코드에서 s_pq는 maxheap, b_pq 는 minheap이다.

 

중간값을 찾아야 하므로 두 큐의 크기는 같아야 한다.

 

예제에서 오른쪽이 top, pop이 일어나는 장소다.

 

ex) 1 2 3 4 5 6 7 8 9를 넣는다면 홀수 번째에서 print

1.

maxheap 1

minheap 

1출력

 

2.

maxheap 1

minheap 2

 

3.

maxheap 1 3(maxheap의  top이 minheap 의 top보다 크므로 둘의 top을 swap)

minheap 2

 

maxheap 1 2

min heap 3

2 출력

 

4.

maxheap 1 2

min heap 4 3

 

5.

maxheap 1 2 5

min heap 4 3 

 

maxheap의 top이 minheap의 top보다 크므로 둘의 top을 swap

maxheap 1 2 3

min heap 5 4

 

3출력

 

6.

maxheap 1 2 3

minheap 6 5 4

 

7.

maxheap 1 2 3 7

minheap 6 5 4

 

7이 4보다 크므로 swap

maxheap 1 2 3 4

minheap 7 6 5

4 출력

 

8. 

maxheap 1 2 3 4

min heap 8 7 6 5

 

9.

maxheap 1 2 3 4 9

minheap 8 7 6 5

 

9가 5보다 크므로 swap

maxheap 1 2 3 4 5

minheap 9 8 7 6

5출력

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,x,tc,p_cnt;
    cin>>tc;
    for(int t=0;t<tc;t++)
    {
        priority_queue<int> s_pq;
        priority_queue<int, vector<int>, greater<int> > b_pq;
        p_cnt = 0;
        cin>>n;
        cout<<n/2+1<<'\n';
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            if(s_pq.size() == b_pq.size())
                s_pq.push(x);
            else
                b_pq.push(x);
            if(!b_pq.empty()&&!s_pq.empty()&&b_pq.top()<s_pq.top())
            {
                int a = s_pq.top();
                int b = b_pq.top();
                s_pq.pop();
                b_pq.pop();
                s_pq.push(b);
                b_pq.push(a);
            }
            if(i%2==1)
            {
                cout<<s_pq.top()<<' ';
                p_cnt ++;
                if(p_cnt % 10 == 0 && n>10)
                    cout<<'\n';
            }
 
        }
        cout<<'\n';
    }
 
    return 0;
}