[백준] 가운데를 말해요

백준 온라인 저지의 1655번 가운데를 말해요 문제 입니다.

문제 출처

가운데를 말해요

문제 해설

n개의 수가 랜덤으로 들어오는데, n이 들어올 때 마다, 중간값을 출력해야한다. 수가 랜덤이기 때문에, 결국 어떠한 방식으로든 정렬을 하긴 해야한다. 그러나 주어진 n의 개수가 100,000개이기 때문에, 매 입력마다 sort()함수를 사용할 수는 없다.(왜냐하면 시간복잡도가 O(n^2)가 되기 때문이다.)

그래서 값을 받을 때 마다 정렬을 하는 자료구조를 써야 한다. 그러나 unordered_set, set, priority_queue 같은 자료구조들은 인덱스 번호에 직접적으로 접근할 수 있는 방법이 없다. 하지만 우리는 중간값만 구하면 되기 때문에, 입력받은 수 들을 중간값 보다 큰수들이 들어있는 그룹, 작은 수들이 들어있는 그룹으로 나누어서 priority_queue에 저장한다음에 가져오는 식으로 할 것이다.

• 최대 힙과 최소 힙을 선언해서 최대 힙에는 작은 수들이 들어있는 그룹을 넣고, 최소 힙에는 큰 수들이 들어있는 그룹을 넣는다.
• 일단 무조건 최대 힙의 크기가 최소힙의 사이즈보다 같거나 1더 많게 할 것이다.
  • 이렇게 함으로써, 무조건 최대 힙의 top()값을 가져오면 그게 답이된다.
• 하지만 이렇게 최대 힙에 넣은 값이, 최소 힙의 top()보다 클 수 있다.
  • 이때, 그냥 최대 힙의 top()값과 최소 힙의 top()값을 바꿔주면 끝이다. 최종적으로 시간복잡도는 n개를 삽입하고, 삽입하는데 걸리는 시간은 lgn이며, top()값이 차이가 있을때 변경해주는 조건문 1이기 때문에 O(nlgn + n) = O(nlgn)이다.

#include <bits/stdc++.h>

using namespace std;

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

	int n; cin >> n;
	priority_queue<int> maxPQ; // 낮은 수들
	priority_queue<int, vector<int>, greater<int>> minPQ; // 높은 수들
	int num; cin >> num; maxPQ.push(num); --n;
	cout << maxPQ.top() << "\n";
	while (n--) {
		int num; cin >> num;
		if (maxPQ.size() > minPQ.size()) minPQ.push(num);
		else maxPQ.push(num);
		if(maxPQ.top() > minPQ.top()) {
			int maxNum, minNum;
			maxNum = maxPQ.top(); maxPQ.pop();
			minNum = minPQ.top(); minPQ.pop();
			minPQ.push(maxNum);
			maxPQ.push(minNum);
		}

		cout << maxPQ.top() << "\n";
	}

	return 0;
}