boj 1655

링크텍스트

처음 생각한 것
:입력을 받아서 배열에 오름차순으로 저장함. 그 후 배열을 순회하면서 인덱스 하나씩 증가할 때마다 그 인덱스 까지 탐색하고 중간값을 찾아서 출력함. 예를 들어 배열 인덱스 0부터 시작하면 그 값이 나오고 다음 인덱스 1까지 탐색하면 둘 중 작은 값을 출력. 인덱스 2까지 보면 숫자 3개 중 중간값을 출력. 인덱스 n에서
n이 짝수일 경우에 숫자는 홀수 개가 있어서 중간값을 출력할 수 있고
배열에 요소를 저장할 때 저장하면서 중간값을 구해서 출력함. 배열의 요소 개수가 홀수일 경우에는 중간값을 구해서 계산하고 짝수일 경우에는 중간값 두개 중 작은 값을 구해서 계산한다.
-> 이 방법은 배열을 순회해 값을 출력하는 시간이 오래 걸릴 것으로 예상됨

vector를 선언해 값을 입력받아 저장한다.
minHeap, maxHeap 두 개를 선언한 뒤 위의 vector의 값을 가져온다.
항상 maxHeap의 top은 minHeap보다 작아야 한다.
maxHeap의 top이 minHeap보다 클 경우 top끼리 바꾸어서 push 해준다.
maxHeap의 top은 중앙값이 된다.
모든 수는 항상 maxHeap + minHeap 으로 정렬이 된 상태이다.

#include
#define endl "\n"
#include

using namespace std;
int main(void)
{
int N;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin >> N; 
vector<int>v(N);

priority_queue<int, vector<int>, greater<int>>minQ;
priority_queue<int>maxQ;
for (int i = 0; i < N; i++)
{
	cin >> v[i];
}

for (int i = 0; i < N; i++)
{
	if (maxQ.size() > minQ.size())
	{
		minQ.push(v[i]);
	}
	else
		maxQ.push(v[i]);

	if (!maxQ.empty() && !minQ.empty())
	{
		if (maxQ.top() > minQ.top())
		{
			int a, b;
			a = maxQ.top();
			maxQ.pop();
			b = minQ.top();
			minQ.pop();
			maxQ.push(b);
			minQ.push(a);
		}
	}
	

	cout << maxQ.top() << endl;
}

return 0;

}