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

 

총 N개의 입력이 들어오고 매번 입력마다 중간값을 출력하는 문제다

N이 최대 10만이기 때문에 N^2은 불가능하다!

 

자료구조 힙을 사용하면 된다

중간만 보기때문에 중간을 기준으로 양쪽을 힙으로 잘랐다고 생각하자

 

계속 첫번째 힙에 숫자를 넣어주고 만약 짝수번째 순서면 두번째 힙으로 넘겨주자

 

그리고 처리할게 하나 있는데 첫번째힙의 탑과 두번째 힙의 탑을 비교해서 

첫번째 힙에 작은수가 들어갈 수 있게 해야한다

그럼 첫번째 힙의  top이 계속 답이된다!

 

참고로 첫번째는 max힙, 두번째는 min힙이다

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n;
int main() {
    scanf(" %d", &n);
    priority_queue<int> pq1, pq2;
    for (int i = 0; i < n; i++) {
        int x; scanf(" %d", &x); 
        pq1.push(x);
        if (i & 1) {
            pq2.push(-pq1.top()); pq1.pop();
        }
        
        if (!pq1.empty() && !pq2.empty()) {
            int a = pq1.top();
            int b = -pq2.top();
            if (a > b) {
                pq1.pop(); pq1.push(b);
                pq2.pop(); pq2.push(-a);
            }
        }
        printf("%d\n", pq1.top());
    }
}