[PS] 백준 1665번: 가운데를 말해요

|

문제

내가 이해한 문제 내용

숫자들이 주어질 때 각 부분수열들에 대한 중앙값을 구하시오.

접근 방식

최대 힙과 최소 힙을 통해서 구현하였다. 최대 힙은 중앙값보다 작은 값들중 최댓값을 유지하는데, 최소 힙은 중앙값보다 큰 값들중 최솟값을 유지하는데 사용하면 중앙값을 쉽게 갱신할 수 있다.

어려웠던 점 & 배운 점

최대 힙의 최솟값과 최소 힙의 최댓값을 생각해내는 점이 까다로웠다.

시간복잡도

$O(log_2N)$

코드

#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

priority_queue<int,vector<int>,less<int> > pq_max;
priority_queue<int,vector<int>,greater<int> > pq_min;

int n,d,ans;

int main(void)
{
    scanf("%d",&n);
    scanf("%d",&d);
    ans = d;
    printf("%d\n",ans);
    for(int i=1; i<n; i++){
        scanf("%d",&d);
        int size = pq_min.size()+pq_max.size()+2;
        if(size%2==0){
            if(d>ans) pq_min.push(d);
            else if(pq_max.size()){
                pq_min.push(ans);
                if(pq_max.top()>d){
                    ans = pq_max.top();
                    pq_max.pop();
                    pq_max.push(d);
                }else{
                    ans = d;
                }
            }else{
                pq_min.push(ans);
                ans = d;
            }
        }else{
            if(d<ans) pq_max.push(d);
            else if(pq_min.size()){
                pq_max.push(ans);
                if(pq_min.top()<d){
                    ans = pq_min.top();
                    pq_min.pop();
                    pq_min.push(d);
                }else{
                    ans = d;
                }
            }
        }

        printf("%d\n",ans);
    }
    return 0;
}