BOJ - 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개씩 출력해야 한다.

예제 입력 1

3
9
1 2 3 4 5 6 7 8 9
9
9 8 7 6 5 4 3 2 1
23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56

예제 출력 1

5
1 2 3 4 5
5
9 8 7 6 5
12
23 23 22 22 13 3 5 5 3 -3
-7 -3

사용할 자료구조

지금까지 입력받은 값의 중앙값을 출력해야하므로 가장 큰 값이 제일 앞으로 오는 우선순위큐를 사용했습니다.

중앙값을 찾아야하므로 중앙값보다 큰 값들을 큐에 임시로 저장해두고 찾은 이후 다시 합치는 식으로 구현하였습니다.

풀이 과정

1) 중앙값은 홀수일 때마다 출력되므로 n이 홀수이면 중앙값의 개수가 n/2+1개고, n이 짝수이면 중앙값의 개수는 n입니다.

2) 홀수 번째 인덱스일 때마다 중앙값을 출력해줍니다.

ex) 9 8 7 6 5 4 3 2 1 의 input을 가질 경우

• 9 ⇒ pq : 9

: pq에 9 삽입 후 0번 pop

• 8 ⇒ pq : 9,8

: 짝수 인덱스이므로 push만 합니다

• 7 ⇒ pq : 9,8,7 ⇒ 8을 출력해야합니다.

: pq에 7 삽입 후 temp 큐에 9를 임시로 넣어둡니다. 한번 pop해주고 top 을 출력합니다.

출력한 이후 temp에 있는 원소들을 pq에 다시 넣어줍니다,

• 6 ⇒ pq : 9,8,7,6

: 짝수 인덱스이므로 push만 합니다,.

• 5⇒pq : 9,8,7,6,5

: pq에 5삽입 후 temp 큐에 9,8 을 임시로 넣어둡니다. 두번 pop해주고 top을 출력합니다.

출력한 이후 temp에 있는 원소들을 pq에 다시 넣어줍니다,

다음과 같은 과정을 반복해줍니다.

시간 복잡도

우선순위큐의 삽입 삭제 연산은 O(logN)만큼 걸리고 큐의 삽입/삭제 연산은 O(1)만큼 걸립니다,.

N번 우선순위큐 삽입 삭제 연산을 하고 N번 큐 삽입 삭제 연산을 하므로 O(NlogN) + O(N) = O(NlogN)만큼의 시간복잡도를 가집니다,.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int m;
        cin>>m;

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

        priority_queue<int> pq;
        queue<int> temp;

        for(int j=1;j<=m;j++){
            int num;
            cin>>num;
            if(j%2==1){
                pq.push(num);
                for(int k=0;k<j/2;k++){
                    temp.push(pq.top());
                    pq.pop();
                }
                cout<<pq.top()<<" ";
                while(!temp.empty()){
                    pq.push(temp.front());
                    temp.pop();
                }
            }else{
                pq.push(num);
            }
        }
        cout<<'\n';
    }

    return 0;
}