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

링크

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

1655번: 가운데를 말해요

해설

사실 이 문제를 풀려면 priority queue 를 2개를 사용한다는 발상이 중요합니다.

왜냐면 우리는 가운데 숫자만 관심이 있지 그 외의 숫자는 별 관심이 없거든요.

 

왼쪽의 priority queue 는 top 이 가장 큰 수가 되게 (내림차순)

오른쪽의 priority queue 는 top 이 가장 작은 수가 되게 (오름차순)

으로 셋팅을 하고 오른쪽 큐를 기준으로 값을 넣고 빼면 됩니다.

이때 지켜야할 규칙이 있는데

1. 오른쪽 큐의 크기 >= 왼쪽 큐의 크기

2. 항상 오른쪽 큐와 왼쪽큐의 최대 크기 차이는 1

 

이 두가지를 지키면서 queue 에 push 하면 됩니다.

 

그러면 왼쪽에는 항상 중간값 보다 작은 값들이 들어가 있고

오른쪽에는 중간값보다 큰 값들이 들어가게 됩니다.

 

오른쪽 큐를 중심으로 잡았으므로

1. 크기가 같으면 짝수개이므로 왼쪽 top, 오른쪽 top 중 작은 것

2. 크기가 다르면 홀수개 이므로 오른쪽 top

이 정답이 됩니다.

 

아래의 코드에 모두 구현되어있습니다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

priority_queue <int> left_que;
priority_queue <int, vector<int>, greater<int>> right_que;

int min(int _a, int _b) { return _a < _b ? _a : _b; }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, temp;
	cin >> N;
	cin >> temp;
	cout << temp << "\n";
	right_que.push(temp);

	for (int i = 1; i < N; ++i) {
		cin >> temp;

		if (left_que.size() == right_que.size()) {
			if (temp >= right_que.top()) {
				right_que.push(temp);
			}
			else {
				left_que.push(temp);
				right_que.push(left_que.top());
				left_que.pop();
			}
			cout << right_que.top() << "\n";
		}
		else {
			if (temp >= right_que.top()) {
				right_que.push(temp);
				left_que.push(right_que.top());
				right_que.pop();
			}
			else {
				left_que.push(temp);
			}
			cout << min(left_que.top(), right_que.top()) << "\n";
		}
		
	}

	return 0;
}