백준 Gold 2 가운데를 말해요

가운데를 말해요 (백준 Gold 2)

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

N개의 수가 1개씩 주어질때
해당 시점에서 그 수들의 ‘중간값’을 구하는 문제

풀이 방법

원래는 Vector를 일일이 정렬하는 방법을 고려할 수 있을듯하나
제한시간이 0.1초이다!

그렇기에 우선순위 큐를 2개 사용하는 방식을 고려하였다

• 최소힙 (내림차순) / 최대힙(오름차순) 을 각각 생성
  

• 최소힙이 비어있거나, 새로 들어오는 수가
  최소힙의 Top보다 작다면 최소힙에 투입
  
  • 이 때, 최소힙이 최대힙보다 2이상 차이나면
    Top을 빼어 최대힙으로 넘겨주기
    
• 새로 들어오는 수가 최소힙의 Top보다 크다면
  최대힙에 투입
  
  • 다만 최대힙의 개수가 최소힙보다 크다면
    최소힙으로 넘겨주기
    
• 마지막으로 최소힙의 Top을 저장해두기
  

이러한 방식을 사용하면
일일이 정렬을 할 필요가 없고
항상 최소힙을 선택하기에
짝수 부분에 연연하지 않을 수 있다

제출 코드

#include<iostream>
#include<queue>

using namespace std;

int main()
{
	priority_queue<int> minQ;
	priority_queue<int, vector<int>, greater<int>> maxQ;
	vector<int> ans;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;

		if (minQ.empty() || t <= minQ.top())
		{
			minQ.push(t);
			if (minQ.size() - maxQ.size() >= 2)
			{
				maxQ.push(minQ.top());
				minQ.pop();
			}
		}
		else // t가 minq의 top보다 큰 상황
		{
			maxQ.push(t);
			if (maxQ.size() > minQ.size())
			{
				minQ.push(maxQ.top());
				maxQ.pop();
			}
		}

		ans.push_back(minQ.top());
	}

	for (int i : ans)
	{
		cout << i << '\n';
	}

	return 0;
}

결과

문제의 제한 사안을 보고 곰곰히 생각하여
답을 찾을 수 있었다!