[GOLD 2] 가운데를 말해요

1. 문제 링크

링크

1655번: 가운데를 말해요

---

2. 문제 이해 및 풀이 전략

매회 하나씩 추가되는 숫자 배열에서 가운데 위치한 숫자를 출력해야하는 문제

 

횟수 N은 1 ~ 100,000 까지의 범위를 가지고 있고 입력되는 정수는 -10,000 ~ 10,000의 범위를 가진다.

 

테스트 케이스로 주어진 숫자 배열, [ 1, 5, 2, 10, -99, 7, 5 ]의 결과로 [ 1, 1, 2, 2, 2, 2, 5 ] 가 출력된다.

 

2 - 1. 시행착오 1

간단히 풀이 방법을 생각해보면

1. 주어진 숫자를 정렬한다.
2. 정렬된 상태에서 가운데 해당하는 숫자를 출력한다.

 

정도로 정리 할 수 있는데 배열의 사이즈가 커질수록 정렬의 과정에서 불필요한 소모가 커질꺼라 예상되어
이를 해결하기 위해 정렬과 삽입에 적은 비용을 들이고, 최소최대값을 구하는데 효과적인 '우선순위 큐(이하 PQ)'에 원소를 담았다.

 

2 - 2. 시행착오 2

PQ로 작성해도 '담겨진 원소중의 중간값'을 구하기 위해선 원소의 첫번쨰만 알 수 있는 상태에서 사이즈의 절반만큼 POP한 후 출력해야하는 불상사가 발생했는데 이마저도 시간초과를 유발하는 원인이였다.

 

때문에 중간값을 찾는 다른 방법을 찾아야됬는데 2개의 PQ를 만들어 하나는 오름차순, 하나는 내림차순으로 만들어 항상 중간값이 하나의 큐에 저장되도록 만드는 것.

 

3.  풀이 코드

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

using namespace std;

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); setvbuf(stdout, nullptr, _IOFBF,BUFSIZ)

int main()
{
	fastio;

	int N;
	priority_queue<int> maxQ;
	priority_queue<int, vector<int>, greater<int>> minQ;

	cin >> N;

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

		if (maxQ.empty() == true)
			maxQ.push(temp);
		else
		{
			if (maxQ.size() > minQ.size())
				minQ.push(temp);
			else
				maxQ.push(temp);

			if (maxQ.top() > minQ.top())
			{
				int tempMax = maxQ.top();
				int tempMin = minQ.top();

				maxQ.pop();
				minQ.pop();

				maxQ.push(tempMin);
				minQ.push(tempMax);
			}
		}

		cout << maxQ.top() << "\n";
	}

	return 0;
}

---

4. 결과 및 회고