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

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

2696번: 중앙값 구하기

---

 

-풀이-

먼저 중앙값 기준으로 왼쪽과 오른쪽 숫자들을 정렬한상태로 저장할 우선순위 큐 2개가 필요하다. left와 right라고 하겠다. left에는 큰값이 우선순위를 부여받도록하고, right에는 작은값이 우선순위를 부여받도록 한다.

1. 데이터를 입력받는다.

2. 데이터를 이용하여 중앙값을 설정해준다. 처음 입력했을땐 중앙값은 입력받은 데이터가 된다.

3. 데이터를 받으면서 중앙값보다 큰 값은 right큐에, 이외의 값은 left큐에 push해준다.

4. 홀수번째 입력을 받았다면 중앙값을 구해주어야 한다.

4-1. 먼저 중앙값을 구하기 위해서 left와 right의 균형을 맞추어 주어야한다. left의 크기보다 right의 크기가 크다면, left큐에 현재 middle값을 push하고, 아니라면 right큐에 middle값을 push한다.

4-2. 이렇게 한다면, left의 크기와 right의 크기의 차이가 0 또는 1이 될것이다. 왜냐하면 두번마다 한번씩 검사를 해주기 떄문에, middle을 push하기전 크기의 차이는 0, 1 또는 2가 된다는 보장이 있기때문이다.

4-3.

middle을 push후에, right의 크기가 left의 크기보다 크다면, 중앙값은 right의 top에 있다는 소리이므로, right의 top을 middle값으로 설정해준뒤 pop해준다.

반대로 left의 크기가 right보다 같거나 크다면, 중앙값은 left에 있다는 소리이므로, left의 top을 middle값으로 설정해준 뒤 pop해준다.

그런 뒤 middle값을 출력해주면된다.

 

-시간복잡도-

priority_queue의 push, pop 시간복잡도는 O(logN)이 된다.

매 i마다 push 혹은 pop, 아니면 둘다 작업을 하므로, 최종 시간복잡도는 O(NlogN)이 된다.

 

-코드-

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

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n,middle;
        priority_queue<int> left,right;
        
        cin>>n;
        cout<<(n+1)/2<<"\n";
        for(int i=1;i<=n;i++){
            int data;
            cin>>data;
            
            if(i==1){
                middle=data;
            }
            else{
                if(data>middle){
                    right.push(-data);
                }
                else{
                    left.push(data);
                }
            }
            
            if(i%2==1){
                if(left.size()<right.size()){
                    left.push(middle);
                }
                else{
                    right.push(-middle);
                }
                
                if(left.size()<right.size()){
                    middle=-right.top();
                    right.pop();
                }
                else{
                    middle=left.top();
                    left.pop();
                }
                
                cout<<middle<<" ";
                if(i%10==0) cout<<"\n";
            }
        }
        cout<<"\n";
    }
   
}