가운데를 말해요

이것도 전 문제처럼 이분탐색을 사용해서 입력값이 주어질 때마다 어느 위치에 들어가야 하는지 계산하고, 배열을 만들어서 중간 인덱스의 값을 가져오면 될거라고 생각했는데, 어느 위치에 들어가야 되는지 계산을 하고 나서 중간 어딘가에 그 값을 넣으려면 배열에 있는 값들을 하나씩 뒤로 밀어야 하는데, 이 과정이 최대 N만큼 시간이 걸리니까 결국 총 시간이 제곱이 되어서 불가능하다는 것을 알게 되었다.

 

결국 풀이를 찾아봤는데 max힙과 min힙을 이용해서 중간값을 찾아야 한다.

간단하게 설명하자면, 수열의 정렬된 상태에서 왼쪽 절반이 max힙, 오른쪽 절반이 min힙에 들어있어야 한다.

그리고 max힙에서 top이 중간값이다.

 

수열에서 숫자를 하나씩 읽어올 때마다 해야 하는 일을 정리해보자면, 값이 중간값보다 크면 min힙에 넣어주고, 작거나 같으면 max힙에 넣어준다. 그리고 max힙의 길이가 전체 개수의 절반보다 크면 min힙으로 옮겨주고, 작으면 min힙에서 max힙으로 옮겨준다.

 

이를 코드로 옮기면 다음과 같다.

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int N;
int ans[100004];
priority_queue<int> maxh;
priority_queue<int, vector<int>, greater<int>> minh;
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        int x;
        scanf("%d",&x);
        if(i==1) maxh.push(x);
        else{
            if(x>maxh.top()){
                minh.push(x);
            }
            else maxh.push(x);
        }
        int m = (i+1)/2;
        while(maxh.size()<m){
            int tmp = minh.top();
            minh.pop();
            maxh.push(tmp);
        }
        while(maxh.size()>m){
            int tmp = maxh.top();
            maxh.pop();
            minh.push(tmp);
        }
        ans[i] = maxh.top();
    }
    for(int i=1;i<=N;i++)
    {
        printf("%d\n",ans[i]);
    }

}