백준 : 1655번 가운데를 말해요 c++

백준 링크

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

1655번: 가운데를 말해요

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.1 초	128 MB	55679	16277	12188	30.364%

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

예제 입력 1

7
1
5
2
10
-99
7
5

예제 출력 1

1
1
2
2
2
2
5

코드 풀이

이번 문제는 최대힙과 최소힙을 사용하여 중간값을 알아내 중간값 중 작은값을 출력하는 문제입니다.

먼저 이 문제를 풀기위한 조건이 있습니다

1. 최대힙의 크기는 항상 최소힙의 크기보다 1만큼 크거나 같아한다.

2. 최대힙의 top값은 항상 최소힙의 top값보다 작거나 같아야한다.

위와 같은 조건을 토대로 정답을 도출하면 아래와 같은 방법이 나오게됩니다

 

TopValue 빨간색 표시

• 최대힙 크기 0, 최소힙 크기 0
  최대힙 [], 최소힙 []
  1번의 조건을 충족하기 위해 첫 1값은 최대힙에 넣어준다.
• 최대힙 크기 1, 최소힙 크기 0
  최대힙 [1], 최소힙[] : 출력 1
  다음 숫자인 5는 1번과 2번의 조건을 전부 충족하기 때문에 최소힙에 저장
• 최대힙 크기 1, 최소힙 크기 1
  최대힙[1], 최소힙[5] : 출력 1
  다음 숫자인 2는 1번의 조건을 충족하기 위해 최대힙에 저장 - 2번의 조건도 자동으로 충족
• 최대힙 크기 2, 최소힙 크기1
  최대힙[2, 1], 최소힙[5] : 출력 2
  다음 숫자인 10은 1번의 조건을 충족하기위해 최소힙에 저장
• 최대힙 크기2, 최소힙 크기2
  최대힙[2, 1]. 최소힙[5, 10] : 출력 2
  다음 숫자인 -99는 1번의 조건을 충족하기위해 최대힙에 저장(자동으로 2번의 조건도 충족)
• 최대힙 크기3, 최소힙 크기2
  최대힙[2, 1, -99], 최소힙[5, 10] : 출력 2
  다음 숫자인 7은 1번의 조건을 충족하기 위해 최소힙에 저장(자동으로 2번의 조건 충족)
• 최대힙 크기3, 최소힙 크기3
  최대힙[2, 1, -99], 최소힙[5, 7, 10] : 출력 2
  다음 숫자인 5는 1번의 조건을 충족하기 위해 최대힙에 저장(자동으로 2번의 조건 충족)
• 최대힙 크기4, 최소힙 크기3
  최대힙[5, 2, 1, -99], 최소힙[5, 7, 10]이된다 : 출력 5

위의 예제에서는 2번의 조건에 충족되지 않는 경우가 없었는데 만약에 최대힙의 top이 최소힙의 top보다 크다면 두 top을 스왑하면 해결이 되게된다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	priority_queue<int, vector<int>> MaxQ;
	priority_queue<int, vector<int>, greater<int>> MinQ;

	int N;
	cin >> N;

	int Number;

	for (int i = 0; i < N; ++i)
	{
		cin >> Number;

		// 처음은 무조건 최대힙
		// 최대힙(내림큐)은 무조건 최소힙의 크기보다 크거나 같아야 되기 때문에
		// 둘의 크기가 같다면 무조건 MaxQ에 넣어야한다.
		if (MaxQ.empty() || MaxQ.size() == MinQ.size())
		{
			MaxQ.push(Number);
		}
		// 그게 아니라면 MinQ에 푸쉬
		else
		{
			MinQ.push(Number);
		}

		// 둘다 비어있지 않고 최대힙이 더 크다면 두 top 스왑
		if (!MinQ.empty() && !MaxQ.empty() && MinQ.top() < MaxQ.top())
		{
			int MinTop = MinQ.top();
			int MaxTop = MaxQ.top();

			MinQ.pop();
			MaxQ.pop();

			MinQ.push(MaxTop);
			MaxQ.push(MinTop);
		}

		cout << MaxQ.top() << '\n';
	}

	return 0;
}