1655번 가운데를 말해요

문제 링크 : www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

---

---

<알고리즘>

  1) 작은 수들(내림차순)과 큰 수들(오름차순)을 구분해서 두개의 priority queue에 각각 집어넣음

  2) 입력 받는 수를 두 개의 queue에 번갈아가면서 input

  3) 만약 작은 수들 중 제일 큰 값이 큰 수들 중 제일 작은 값보다 클 때 두 수를 swap

      (작은 수 들 중 제일 큰 값< 큰 수들 중 제일 작은 값 일때까지)

  4) 결국 중앙 값은 작은 수들 중 제일 큰 값이므로 small prioirty queue의 top 출력

 

 

 

메모리 : 2784KB    시간 28ms 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
	ios_base ::sync_with_stdio(false);
	cin.tie(0);

	int N = 0;
	cin >> N;

	priority_queue<int, vector<int>, less<int>> small;
	priority_queue<int, vector<int>,  greater<int>> big;
	int a = 0;

	while (N--) {
		cin >> a;
		
		if (small.size()>big.size()) {
			big.push(a);
		}
		else {
			small.push(a);
		}
		
		while (!small.empty() && !big.empty() &&!(small.top() <= big.top())) {
			int temp = small.top();
			small.pop();
			int temp2 = big.top();
			big.pop();
			small.push(temp2);
			big.push(temp);	
		}
		cout << small.top() << "\n";
	}
	return 0;
}