백준 1655- 가운데를 말해요

 

 

문제 설명

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

예를 들어 백준이가 동생에게 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개의 수를 N번 정렬해야 하기 때문에 $N^2log(N)$의 시간복잡도를 가진다.

즉, 시간초과가 발생할 수 있다.

 

이 문제를 풀기 위해서는 아이디어가 필요하다.

현재 중간값보다 작은 수와 큰 수를 분리한다면 중간값을 쉽게 찾을 수 있다.

중간값보다 작은 수와 큰 수의 차이가 2개 이상 벌어지면 중간값이 갱신된다.

예를 들어, {1, 5, 2, 10, -99, 7, 5}라는 입력이 주어질 때, 첫 수인 1은 해당 값이 중간값이 된다.

이후 5라는 입력이 들어오면, 현재 중간값인 1보다 크기 때문에 큰 수로 분리한다.

이후, 2라는 입력이 들어오면, 역시 큰 수로 분리된다.

이때, 현재 중간값보다 큰 값이 2개 작은 값이 0개이다.

따라서, 현재 중간값보다 큰 수 중 가장 작은 수가 현재 중간값이 된다.

 

이러한 원리로 입력이 들어올 때마다 중간값을 갱신해 주면 된다.

하지만, 주의할 점이 한 가지 있다.

배열의 길이가 짝수라면, 두 개의 중간값이 생기는데 이중 작은 값을 선택해야 한다.

이런 예외를 처리하는 방법은 간단하다.

앞에서 중간값을 갱신할 때, 중간값보다 큰 수는 작은 수보다 2개 많으면, 작은 수는 큰 수보다 많아질 때 갱신한다.

예를 들어, 작은 수에 2개 큰 수에 2개가 있는 상황에서 현재 중간값보다 작은 수가 입력되었다고 가정해 보자.

이러한 상황에서 중간값은 3 혹은 4가 될 수 있다.

하지만, 문제에서 제시한 조건은 둘 중 작은 수를 골라야 하기 때문에 작은 수가 큰 수보다 많아지면 갱신해야 한다.

 

이러한, 작업을 쉽게 할 수 있는 자료구조는 priority_queue이다.

pq는 Heap을 기반으로 만들어졌기 때문에 정렬에 $Nlog(N)$이 걸리고, 가장 큰 수 혹은 가장 작은 수를 제어하기도 쉽다.

pq는 기본적으로 내림차순으로 정렬된다.

현재 중간값보다 큰 수는 가장 작은 수를 뽑아와야 하고, 현재 중간값보다 작은 수는 가장 큰 수를 뽑아야 하기 때문에 다음과 같이 설정한다.

priority_queue<int> Smaller;
priority_queue<int, vector<int>, greater<int>> Bigger;

greater<int>로 설정하게 되면 오름차순으로 정렬된다.

즉, 가장 작은 수부터 pop된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	int currentMid = 0;
	
	priority_queue<int> Smaller;
	priority_queue<int, vector<int>, greater<int>> Bigger;

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

		if (i == 0)
		{
			currentMid = temp;
			cout << currentMid << "\n";
			continue;
		}

		if (temp > currentMid) Bigger.push(temp);
		else Smaller.push(temp);

		int BiggerCnt = Bigger.size();
		int SmallerCnt = Smaller.size();

		if (BiggerCnt > SmallerCnt + 1)
		{
			Smaller.push(currentMid);
			currentMid = Bigger.top();
			Bigger.pop();
		}
		else if (SmallerCnt > BiggerCnt)
		{
			Bigger.push(currentMid);
			currentMid = Smaller.top();
			Smaller.pop();
		}

		cout << currentMid << '\n';
	}

	return 0;
}

---