이 문제에서는 지속적으로 정수를 읽는 데이터 스트림이 제공됩니다. 우리의 임무는 요소를 읽고 이러한 요소의 중앙값을 계산하는 프로그램을 만드는 것입니다.
중앙값 배열의 중간 요소는 정렬된 시퀀스의 중간 요소입니다(오름차순 또는 내림차순일 수 있음).
중앙값 계산
홀수 개수의 경우 중앙값은 중간 요소입니다.
짝수 개수의 경우 중앙값은 중간 요소 2개의 평균입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - 3, 65, 12, 20, 1
각 입력에서
Input - 3 : sequence -(3) : median - 3 Input - 65 : sequence -(3, 65) : median - 34 Input - 12 : sequence -(3, 12, 65) : median - 12 Input - 20 : sequence -(3, 12, 20, 65) : median - 16 Input - 1 : sequence -(1, 3, 12, 20, 65) : median - 12
중앙값 계산을 쉽게 하기 위해 정렬된 순서를 사용했습니다.
이 문제를 해결하기 위해 각 단계에서 정렬을 사용한 다음 중앙값 찾기, 자체 균형 BST 생성 또는 힙 사용을 사용하는 여러 솔루션이 있습니다. 힙은 중앙값을 찾는 가장 유망한 솔루션인 것 같습니다. max-heap 또는 min-heap은 모두 삽입할 때마다 중앙값을 제공할 수 있으며 효과적인 솔루션이기도 합니다.
예시
솔루션 구현을 보여주는 프로그램,
#include <iostream>
using namespace std;
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
bool Greater(int a, int b){
return a > b;
}
bool Smaller(int a, int b){
return a < b;
}
int Signum(int a, int b){
if( a == b )
return 0;
return a < b ? -1 : 1;
}
class Heap{
public:
Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)
{ heapSize = -1; }
virtual bool Insert(int e) = 0;
virtual int GetTop() = 0;
virtual int ExtractTop() = 0;
virtual int GetCount() = 0;
protected:
int left(int i) {
return 2 * i + 1;
}
int right(int i) {
return 2 * (i + 1);
}
int parent(int i) {
if( i <= 0 ){
return -1;
}
return (i - 1)/2;
}
int *A;
bool (*comp)(int, int);
int heapSize;
int top(void){
int max = -1;
if( heapSize >= 0 )
max = A[0];
return max;
}
int count() {
return heapSize + 1;
}
void heapify(int i){
int p = parent(i);
if( p >= 0 && comp(A[i], A[p]) ) {
swap(A[i], A[p]);
heapify(p);
}
}
int deleteTop(){
int del = -1;
if( heapSize > -1){
del = A[0];
swap(A[0], A[heapSize]);
heapSize--;
heapify(parent(heapSize+1));
}
return del;
}
bool insertHelper(int key){
bool ret = false;
if( heapSize < MAX_HEAP_SIZE ){
ret = true;
heapSize++;
A[heapSize] = key;
heapify(heapSize);
}
return ret;
}
};
class MaxHeap : public Heap {
private:
public:
MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }
int GetTop() {
return top();
}
int ExtractTop() {
return deleteTop();
}
int GetCount() {
return count();
}
bool Insert(int key) {
return insertHelper(key);
}
};
class MinHeap : public Heap{
private:
public:
MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { }
int GetTop() {
return top();
}
int ExtractTop() {
return deleteTop();
}
int GetCount() {
return count();
}
bool Insert(int key) {
return insertHelper(key);
}
};
int findMedian(int e, int &median, Heap &left, Heap &right){
switch(Signum(left.GetCount(), right.GetCount())){
case 0: if( e < median ) {
left.Insert(e);
median = left.GetTop();
}
else{
right.Insert(e);
median = right.GetTop();
}
break;
case 1: if( e < median ){
right.Insert(left.ExtractTop());
left.Insert(e);
}
else
right.Insert(e);
median = ((left.GetTop()+right.GetTop())/2);
break;
case -1: if( e < median )
left.Insert(e);
else {
left.Insert(right.ExtractTop());
right.Insert(e);
}
median = ((left.GetTop()+right.GetTop())/2);
break;
}
return median;
}
void printMedianStream(int A[], int size){
int median = 0;
Heap *left = new MaxHeap();
Heap *right = new MinHeap();
for(int i = 0; i < size; i++) {
median = findMedian(A[i], median, *left, *right);
cout<<"Median of elements : ";
for(int j = 0; j<=i;j++) cout<<A[j]<<" ";
cout<<"is "<<median<<endl;
}
}
int main(){
int A[] = {12, 54, 9, 6, 1};
int size = ARRAY_SIZE(A);
printMedianStream(A, size);
return 0;
} 출력
Median of elements : 12 is 12 Median of elements : 12 54 is 33 Median of elements : 12 54 9 is 12 Median of elements : 12 54 9 6 is 10 Median of elements : 12 54 9 6 1 is 9