[1655] 가운데를 말해요

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

1655번: 가운데를 말해요

<문제>

N : 10만, 시간제한 0.1초로 사실상 O(n)이하의 시간복잡도를 갖는 풀이를 구상해야 한다.

입력을 받자마자 상수시간내에 중간값을 계산해야 한다는 생각은 했지만, 정작 처음에는 우선순위큐도 생각이 안났다.

 

일반적으로 2개의 우선순위큐를 만드는데 하나는 오름차순, 하나는 내림차순으로 만든다.

최대힙과 최소힙을 만들고, 아래의 규칙을 지키도록 입력된 숫자를 적절한 곳에 넣으면 된다.

1)최대힙의 크기는 최소힙의 크기와 같거나 1만큼 크다.

2)최소힙의 모든 값은 최대힙의 모든 값보다 크다.

 

1번조건을 만족시키려면, 최대힙과 최소힙의 크기가 같다면 항상 최대힙에 넣어주기만 하면 된다.

2번조건을 만족시키려면, 최대힙의 top이 최소힙의 top보다 크다면, 이 둘을 swap하면 된다.
입력을 받자마자 매번 이 과정을 커지면, top간의 비교만으로 항상 2번조건을 만족시키게 유지할 수 있다.

 

위와같이 두개의 힙에 데이터를 넣어주면, 우리가 구해야 하는 답은 최대힙의 top이 된다.

<소스코드>

#include<stdio.h>
#include<queue>
#include<math.h>
using namespace std;
 
priority_queue <int    , vector<int>, greater<int>> min_q;
priority_queue <int> max_q;
 
int main(void) {
    int n, i, x;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        if (max_q.size() == min_q.size())
            max_q.push(x);
        else
            min_q.push(x);
        if (!max_q.empty() && !min_q.empty() && max_q.top() > min_q.top()) {
            int a = max_q.top();
            int b = min_q.top();
            max_q.pop();
            min_q.pop();
            max_q.push(b);
            min_q.push(a);
        }
        printf("%d\n", max_q.top());
    }
    return 0;
}