[BOJ] 1655 : 가운데를 말해요 - travelbeeee

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

---

[알고리즘풀이]

내림차순으로 정렬되는 Priority_Queue와 오름차순으로 정렬되는 Priority_Queue 2개를 이용해서 문제를 해결할 수 있습니다. 편의상 내림차순으로 정렬되는 Priority_Queue를 pq1 / 오름차순을 pq2 라고 하겠습니다.

pq1 은 중앙값보다 작거나 같은 수들을 담을 것이고, pq2는 중앙값보다 큰 수들을 담을 것입니다.

따라서, 위의 그림과 같은 상황이 됩니다.

 

입력이 들어오면 새로운 입력은 Mid보다 크거나 / 작거나 같습니다.

1) Mid보다 입력이 큰 경우.

입력이 Mid보다 크다면, 새로운 입력은 pq2에 Push되야합니다.

이때, pq2가 pq1보다 2개 이상 많아진다면 Mid에 영향을 주게 됩니다.

즉, Mid를 pq1에 Push해주고, pq2에서 가장 작은 값( pq2.top() )이 새로운 Mid가 됩니다.

예시를 통해 자세히 알아보겠습니다. 다음과 같은 상황이라고 해봅시다.

-2 -1 / 0 / 1 2 3

4가 새롭게 입력으로 들어온다면, -2 -1 0 / 1 / 2 3 4 로 Mid가 바뀌게 됩니다.

이 외에는 Mid에 변화가 없습니다.

 

2) Mid보다 작거나 같은 경우.

새로운 입력을 pq1에 Push되야합니다.

1)과 마찬가지로 이때, pq1이 pq2보다 커진다면 Mid에 영향을 주게 됩니다.

이번엔 반대로 Mid가 작아져야 합니다. 따라서, 현재 Mid를 pq2에 push해주고, pq1에서 새로운 Mid를 가져옵니다.

예시를 통해 자세히 알아보겠습니다. 다음과 같은 상황이라고 해봅시다.

-2 -1 0 / 1 / 2 3 4

-4가 새롭게 입력으로 들어온다면 -4 -2 -1 / 0 / 1 2 3 4 로 pq1에서 새로운 Mid를 가져와야 합니다.

이 외에는 Mid에 변화가 없습니다.

 

우선순위 큐를 위와 같이 2개를 이용하면 문제가 간단하지만, 이 아이디어를 생각하기까지 시간이 오래 걸렸던 문제입니다.

#include<iostream>
#include<queue>

using namespace std;

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

	int n, mid, x;
	priority_queue<int> pq1;
	priority_queue<int, vector<int>, greater<int>> pq2;

	cin >> n >> mid;
	cout << mid << '\n';
	for (int i = 1; i < n; i++) {
		cin >> x;
		if (x > mid) {
			pq2.push(x);
			if (pq1.size() == pq2.size() - 2) {
				pq1.push(mid);
				mid = pq2.top();
				pq2.pop();
			}
		}
		else {
			pq1.push(x);
			if (pq1.size() > pq2.size()) {
				pq2.push(mid);
				mid = pq1.top();
				pq1.pop();
			}
		}
		cout << mid << '\n';
	}
}

---