[C/C++] 백준 #1655 가운데를 말해요(힙)

이번 문제는 구간의 중간수 구하던 문제와 같이 두개의 힙을 이용해서 풀 수 있는 문제입니다.

 

왼쪽은 최대힙(max heap)을 오른쪽은 최소힙(min heap)을 운영합니다.  왼쪽 힙은 오른쪽 힙의 개수보다 1개 크거나 같아야 합니다.

 

min heap vs. max heap

 

1, 5, 2, 10, -99, 7, 5 순으로 숫자가 불리었고, 이번에 10이 불리는 차례였다면, 왼쪽의 최대힙은 [ 2, 1 ] 이 들어가 있고, 오른쪽 최소힙은 [5]가 들어가 있습니다.  10을 왼쪽힙의 최대값 2와 비교해서 작으면 왼쪽에, 크면 오른쪽에 넣습니다.  이 경우엔 2보다 큰 수이므로 오른쪽에 들어가 있게 됩니다.  그러면 [ 2, 1 ]과 [ 5, 10 ] 이 되고, 두 힙의 크기가 같으니, 힙간 원소 이동은 없습니다.  왼쪽힙의 가장 큰 값을 출력하면 2가 되겠죠.  다음은 -99입니다.  이 숫자는 2보다 작으므로 왼쪽 힙에 들어가서 [2, 1, -99]와 [5, 10]이 됩니다.  왼쪽 힙의 개수가 1개 크므로, 힙간 원소 이동이 없고 2를 출력하면, 됩니다.  다음은 7을 넣으면 [2, 1, -99]와 [ 5, 7, 10 ]이 되어서 역시 2가 출력되죠.  다음은 5를 넣어야 하는데, 5는 오른쪽에 들어가야 합니다.  [2, 1, -99]와 [5, 5, 7, 10]이 되고, 오른쪽 힙이 크므로 원소 이동을 합니다.  [ 5, 2, 1, -99]와 [ 5, 7, 10]이 되어 5를 출력하면 됩니다.

 

최대힙과 최소힙을 적절하게 사용하면 되는 문제이고, 구간별 중간값을 구하는 것보다는 쉽습니다.

 

이라는 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1655 - Say Median
//        - by Aubrey Choi
//        - created at 2019-08-06
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

bool cmp(int a, int b) { return a>b; }

int main()
{
    int n, s;
    int a[50004], b[50004], ac=0, bc=0;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d", &s);
        if(ac==0||a[0]>=s) { a[ac++]=s; std::push_heap(a,a+ac); }
        else { b[bc++]=s; std::push_heap(b,b+bc,cmp); }
        if(ac>bc+1) { std::pop_heap(a,a+ac); b[bc++]=a[--ac]; std::push_heap(b,b+bc,cmp); }
        if(ac<bc) { std::pop_heap(b,b+bc,cmp); a[ac++]=b[--bc]; std::push_heap(a,a+ac); }
        printf("%d\n", a[0]);
    }
}