[백준 1655] 가운데를 말해요

문제

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

문제 풀이

 

1. 항상 중앙 값을 구하기 위해 우선순위 큐 두 개를 아래의 그림과 같이 사용해서 입력받는 수를 관리하기로 한다.

• lpq = top쪽으로 갈수록 수가 커지는 max heap

• rpq = top쪽으로 갈수론 수가 작아지는 min heap

2.  입력받는 수(k)는 항상 두 힙중 하나에 들어가야하며 중앙값을 구하기위해 두 힙의 크기는 항상 같거나 lpq가 rpq보다 크기가 1큰 경우만 만족할 수 있도록 수가 들어올때마다 적절히 힙을 조절한다.

•  수가 처음 들어올 때 : lpq에 저장

•  $lpq.size() >= rpq.size()$ 일 때 : rpq.top()와 k의 대소비교를 통해 어느 힙에 넣을지 정해주고 두 힙의 크기조정

•  $lpq.size() < rpq.size()$ 일 때 :  두 힙의 크기가 같을 때 k가 들어온 경우 항상 lpq의 크기가 크도록 조정했으므로 나올수 없음.

3. 지금까지 들어온 수의 개수가 홀수이면 lpq.top을, 짝수면 (lpq,rpq).top중 작은 것을 중앙값으로 저장

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, k, temp;
priority_queue<int, vector<int>> lpq;
priority_queue<int, vector<int>, greater<>> rpq;
vector<int> ans;

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> k;
		if (i == 1) lpq.push(k);
		else {
			if (lpq.size() == rpq.size()) {
				temp = rpq.top();
				if (temp <= k) rpq.pop(), lpq.push(temp), rpq.push(k);
				else lpq.push(k);
			}
			else if (lpq.size() > rpq.size()) {
				temp = lpq.top();
				if (temp >= k) lpq.pop(), rpq.push(temp), lpq.push(k);
				else rpq.push(k);
			}
		}
		if (i % 2) ans.push_back(lpq.top());
		else ans.push_back(min(lpq.top(), rpq.top()));
	}
	for (int i : ans) cout << i << " ";
}