[baekjoon 2696] 중앙값 구하기 (우선순위 큐) (C++)

https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

어떤 수열을 읽고, 홀수번째 수를 읽을 때마다, 지금까지 입력받은 값의 중앙값을 출력하는 문제이다.

 

수가 입력될 때마다, 정렬해서 입력받은 값을 출력하기보다 우선순위 큐를 이용하면 매번 정렬 대신 전체 데이터를 nlogn만에 풀이가 가능하다.

 

maxHeap은 top에 가장 큰 값이 저장되고, minHeap은 top에 가장 작은 값이 저장된다.

 

minHeap과 maxHeap 두 개를 선언한 뒤, 데이터를 넣어주는데

항상 maxHeap의 top은 minHeap의 top보다 작아야 한다.

그리고 maxHeap -> minHeap -> maxHeap -> minHeap 순서로 삽입을 해준다.

maxHeap은 항상 홀수번째 수가 삽입되고 maxHeap의 top은 중앙값이 된다.

모든 수는 항상 maxHeap + minHeap으로 정렬이 된 상태가 된다.

1 2 3 4 5 6 7 8 9의 과정을 그림으로 표현하면 

 

화살표의 방향이 top이다.

1이 maxHeap에 삽입되고, 2는 minHeap에, 3은 다시 maxHeap에 삽입된다.

하지만 3이 maxHeap에 삽입되는 순간 maxHeap의 top이 minHeap의 top보다 크므로 바꿔준다.

minHeap은 위, maxHeap은 아래라고 하겠다.

4는 minHeap(위)에 삽입되고, 5가 아래에 삽입된다. 

두 번째를 보면 역시 아래의 top이 위의 top보다 크기 때문에 top끼리 바꿔서 push 해준다.

 

역시 7을 삽입하면 전체적으로 정렬이 깨지고, top끼리 바꿔준다.

9를 삽입해도 마찬가지로 바꿔주고 항상 아래의 top이 중간값이다.

마지막 그림을 보면 maxHeap + minHeap의 데이터가 정렬된 상태임을 볼 수 있다.

 

그리고 우리가 원하는 수는 우선순위 큐 두 개의 경계 부분에 항상 저장되어 있음을 확인할 수 있다.

 

+참고로 이 문제는 10개씩 잘라서 출력하라고 했는데 그러면 출력 오류로 틀렸다고 뜬다.

그냥 저장된 값을 띄어쓰기 포함해서 다 출력해주면 correct가 뜬다.

 

#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;

ll T, n, num;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> n;
		vector<ll> answer;
		priority_queue<ll, vector<ll>, greater<ll>> down;
		priority_queue<ll> up;
		for (int i = 1; i <= n; i++) {
			cin >> num;
			if (i % 2 != 0) { // 홀수번째는 아래 maxHeap에 삽입
				up.push(num);
				if (!up.empty() && !down.empty()) {
					if (up.top() > down.top()) { // 아래 삽입 후 top끼리 대소관계 비교
						down.push(up.top());
						up.pop();
						up.push(down.top());
						down.pop();
					}
				}
			}
			else {
				down.push(num);
			}
			if (i % 2 != 0) { // 홀수번째마다 중앙값을 저장해준다.
				answer.push_back(up.top());
			}
		}
		cout << answer.size()<<"\n";
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << " ";
		}
		cout << "\n";
	}
}

+우선순위 큐 두개를 사용해서 푸는 거의 똑같은 문제이다.

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요