중앙값

중앙값 구하기

c++ 백준 문제 푸는 겸 만든 중앙값을 구하기 위한 큐

#include <iostream>
#include <vector>
#include <queue>

class MedianQueue{
private:
	std::priority_queue<int> smallerQueue; // 중앙값보다 작은 값들을 보관하는곳(중앙값도 여기에 보관)
	std::priority_queue<int, std::vector<int>, std::greater<int>> biggerQueue;
	// 중앙값보다 큰 값을 보관하는 곳, 기본적으로 큰값이 먼저 나오기 때문에 반대로 나오도록 설정
	//smallerQueue가 biggerQueue보다 개수가 1개 많도록 유지한다.
public:
	void push(int value);
	void pop();
	double top();
};

void MedianQueue::push(int value){
	if(smallerQueue.size() == 0){ // smallerQueue는 기준이 저장 될 것이기 때문에 최소 biggerQueue보다 개수가 1개 많거나 같아야한다.
		smallerQueue.push(value);
	}
	else if(smallerQueue.top() > value){ // 기준점보다 작으면 smallerQueue에 보관
		smallerQueue.push(value);
	}
	else { // 기준점보다 크면 biggerQueue에 보관
		biggerQueue.push(value);
	}
	
	if(smallerQueue.size() < biggerQueue.size()){ // smallerQueue이 biggerQueue보다 개수가 1개 많거나 같도록 조정
		smallerQueue.push(biggerQueue.top());
		biggerQueue.pop();
	}
	else if(smallerQueue.size() - 1 > biggerQueue.size()){
		biggerQueue.push(smallerQueue.top());
		smallerQueue.pop();
	}
}

double MedianQueue::top(){
	if(smallerQueue.size() == biggerQueue.size()){ // 입력된 값의 개수가 짝수일경우 두 큐의 값의 평균을 반환 
		return (double)(smallerQueue.top() + biggerQueue.top() ) / 2;
	}
	else {
		return smallerQueue.top();
	}
}

void MedianQueue::pop(){ // 짝수일 경우 가운데 2개의 값을 제거, 홀수 일 경우 중앙값만 제거
	if (smallerQueue.size() == biggerQueue.size()) {
		smallerQueue.pop();
		biggerQueue.pop();
	}
	else {
		smallerQueue.pop();
	}
}