[c++] 백준 - 1655 가운데를 말해요(우선순위 큐)

1. 문제

2. 입력 및 출력

---

3. 문제 해설

priority_queue를 적절히 사용하여 중간값을 찾아내면 되는 문제였다. 

우선 중간값을 찾아야한다는 점에서 pq가 두 가지가 필요하다는 것을 알 수 있었다. 

 

우리는 최대힙과 최소힙을 각각 하나씩 선언하여 중간을 찾아내면 된다. 

그런데 문제에서 만약 짝수개가 들어갔을 경우에는 더 작은 값을 찾아내라 했으니 정답은 최대 힙에 들어있을 수 있을 것이다. 

 

왜냐하면 pq에서 접근할 수 있고 의미가 있는 값은 pq.top()에 해당하는 부분이다. top()이 항상 답이 되게 하려면

우리는 다음과 같이 pq를 구성해야한다. 

 

만약 1 5 2 10 이라는 수열을 기준으로 봤을 때

정렬을 하면 1 2 5 10이 되고 이 기준에서 중간값은 2에 해당한다.

pq.top()이 2가 되게 하려면 다음과 같이 구성하면 될 것이다. 

우선 2보다 작은 1은 최대 힙에 집어 넣는다. 

 

최대 힙 : 2->1

최소 힙: 5->10

 

다음과 같이 구성하면 우리는 두 개의 힙을 이용해서 정렬이 된 거 같은 효과를 낼 수 있다. 여기서 -99라는 값이 들어오면 어디로 가야할까? 1보다 작은 수이기 때문에 또한 우리는 최대 힙의 top을 답으로 간주하고 있기 때문에 최대 힙에 삽입을 해야할 것이다. 

 

최대 힙 :2->1->-99

최소 힙:5->10

 

만약 이 상태에서 7이 들어온다면 

 

최대 힙 : 2->1->99

최소 힙 : 5->7->10이 될 것이다. 여기서 알 수 있는 점은 

 

최대 힙의 크기가 항상 최소 힙의 크기보다 1크거나 같아야한다는 점이다. 당연히 중간을 구하는 것이기 떄문에 그럴 것이다. 

 

만약 그런데 이런 경우를 생각해보자

 

1 5 2 -99와 같은 수열이 존재할 때는 어떻게 될까?

 

우선 최대힙의 크기가 더 커야하기 때문에

 

최대 힙 : 1

최소 힙 : 

 

다음과 같이 진행되고

최대 힙 : 1

최소 힙 : 5

 

최대 힙 : 2->1

최소 힙 : 5

 

최대 힙 : 2->1

최소 힙 : -99->5가 되어 버린다. 이것은 답과 맞지 않다. 

왜냐하면 우리가 정렬을 하는 것과 비슷한 효과를 얻고자 두 개의 pq를 사용하는데 최대힙의 top을 기준으로 최대힙에는 pq.top보다 작거나 같은 수만 들어가있고

최소 힙에는 최대힙의 top보다 크거나 같은 수만들어갈 수 있기 때문이다. 

 

위를 정렬한 것처럼 쓰면 1->2->-99->5가 된다. 이 경우에는 최대힙의 top과 최소 힙의 top을 교환해주면 된다. 

 

그러면 

최대 힙 : 1->-99

최소 힙 : 2->5

 

가 되어 올바른 답 1이 될 것이다. 

 

---

4. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <queue>
using namespace std;
int N;
priority_queue<int, vector<int>, greater<>> minpq;
priority_queue<int, vector<int>> maxpq;
void sol() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int temp = 0;
		scanf("%d", &temp);
		if (minpq.size() == maxpq.size()) {
			maxpq.push(temp);
		}
		else if (minpq.size() + 1 == maxpq.size()) {
			minpq.push(temp);
		}

		if (minpq.size() && minpq.top() < maxpq.top()) {
			//만약 최소힙의 top보다 최대 힙의 top이 더 커진다면 swap
			int temp = minpq.top();
			int temp2 = maxpq.top();
			minpq.pop();
			maxpq.pop();
			minpq.push(temp2);
			maxpq.push(temp);
		}
		printf("%d\n", maxpq.top());
	}
}
int main() {
	sol();
	return 0;
}