[백준 1655] 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

중간값 찾기 알고리즘을 사용한다.

 

maxHeap과 minHeap이 필요해서 우선순위큐를 사용한다.

두 힙은 다음과 같은 규칙을 따른다.

 

1. maxHeap은 minHeap의 크기와 같거나 1만큼 크다.

2. maxHeap의 탑은 minHeap의 탑보다 작거나 같다. 만약 이를 만족시키지 못하면 둘을 바꾼다.

 

이렇게 하면 maxHeap의 탑이 항상 중간값임을 알 수 있다. 신기방기..

 

예제에 적용하면 (오른쪽이 maxHeap이다.)

1: [] [1]

2: [5] [1]

3: [5] [2, 1]

4: [10, 5] [2, 1]

5: [10, 5] [2, 1, -99]

6: [10,7,5] [2,1,-99]

7: [10,7,5] [5,2,1,-99]

 

이렇게 된다.

 

#include <stdio.h>
#include <queue>

using namespace std;
int n;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    int tmp;
    scanf("%d", &tmp);

    if (maxHeap.size() <= minHeap.size())
    {
      maxHeap.push(tmp);
    }
    else
    {
      minHeap.push(tmp);
    }

    if (!maxHeap.empty() && !minHeap.empty())
    {
      int max = maxHeap.top();
      int min = minHeap.top();
      if (max > min)
      {
        maxHeap.pop();
        minHeap.pop();
        maxHeap.push(min);
        minHeap.push(max);
      }
    }

    printf("%d\n", maxHeap.top());
  }
  return 0;
}