BOJ 1655: 가운데를 말해요 작성일 2020-02-22 https://www.acmicpc.net/problem/1655 2월동안 187문제 풀기(지난달 누적 87개) (49/187) 유명한 Running Median 문제. 직접 구현한 Heap을 써봄. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include <bits/stdc++.h> using namespace std; class Heap { int data[100001]; int bound; int type; inline int LS(int a) { return 2*a; } inline int RS(int a) { return 2*a+1; } inline int PA(int a) { return a/2; } inline void swap(int x, int y) { int tmp = data[x]; data[x] = data[y]; data[y] = tmp; } inline int max(int x, int y){ if (type == 0) return data[x] > data[y] ? x : y; else return data[x] < data[y] ? x : y; } inline int max(int x, int y, int z) { return max(x, max(y, z)); } public: Heap(int _type) { type = _type; memset(data, type ? INT_MAX : INT_MIN, sizeof(data)); bound = 1; } int size() { return bound-1; } int top() { return data[1]; } void push(int x) { int pos = bound; data[bound++] = x; while (max(pos, PA(pos)) == pos && pos > 1) { swap(pos, PA(pos)); pos = PA(pos); } } int pop() { if (bound == 1) return 0; int pos = 1, ret = data[1]; data[1] = data[--bound]; data[bound] = type ? INT_MAX : INT_MIN; while(LS(pos) < bound || RS(pos) < bound) { int m = max(pos, LS(pos), RS(pos)); if (m == pos) break; swap(m, pos); pos = m; } return ret; } }; int N, x; int main() { ios::sync_with_stdio(false); cin >> N; Heap maxHeap(0), minHeap(1); for(int i = 0; i < N; i++) { cin >> x; if (maxHeap.size() == minHeap.size()) maxHeap.push(x); else minHeap.push(x); if(minHeap.size() && maxHeap.top() > minHeap.top()) { minHeap.push(maxHeap.pop()); maxHeap.push(minHeap.pop()); } printf("%d\n", maxHeap.top()); } }