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

1655번: 가운데를 말해요

 

 

문제풀이

 

정수를 하나씩 받을 때마다 중앙값을 출력하는 문제다.

이 문제는 우선순위 큐 2개를 이용해서 풀 수 있다.

 

기본적으로 우선순위 큐가 Heap 구조이므로 Max Heap과 Min Heap 두 개를 선언한다.

비교함수를 따로 정해주지 않으면 기본적으로 내림차순에 따라 정렬한다. (Max Heap)

 

// Min Heap
priority_queue<int, vector<int, int>, greater<int>> minheap;
// Max Heap
priority_queue<int> maxheap;

 

중간값을 찾아야 하므로 두 큐의 크기는 같아야 한다.

우선 입력 받은 정수를 두 큐의 크기가 같도록 큐에 넣어준다.

 

그 후 max heap의 top과 min heap의 top을 비교했을 때 min heap의 top이 더 크다면

정렬이 제대로 되지 않은 상태이므로 max heap과 min heap의 top을 swap해준다.

 

수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말하면 되므로

짝수든 홀수든 max heap의 top을 출력해주면 된다.

 

 

C++ 코드

 

	#include <iostream>
	#include <queue>
	using namespace std;
	int main()
	{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n;
	priority_queue<int> maxheap; // 중간값보다 큼
	priority_queue<int, vector<int>, greater<int>> minheap; // 중간값보다 작음
	for (int i = 1; i <= n; i++) {
	cin >> k;
	if (maxheap.size() == minheap.size())
	maxheap.push(k);
	else
	minheap.push(k);
	if (!maxheap.empty() && !minheap.empty() && minheap.top() < maxheap.top()) {
	int a = minheap.top();
	int b = maxheap.top();
	minheap.pop(); maxheap.pop();
	minheap.push(b);
	maxheap.push(a);
	}
	cout << maxheap.top() << '\n';
	}
	return 0;
	}

view raw [BOJ 1655] 가운데를 말해요.cpp hosted with ❤ by GitHub