C++ [가운데를 말해요_백준] / #priority_queue

Problem

---

- 보기에는 간단해보이지만 쉽지 않은 문제였다.

- 처음은 vector에 수를 넣고 넣을때마다 sort를 통해 정렬한 뒤 vec[i/2]로 가운데 인자에 접근했었으나 시간초과로 계속 실패했었다.

- 구글링을 통해 힌트를 얻어 해결하였다.

- 풀이법은 간단하면서 획기적이어서 충격이었다.

 

Solve

---

- 우선 priority_queue 2개가 필요하다.

- 하나는 중간값보다 작은 수들이 들어갈 우선순위 큐(작은 큐), 다른 하나는 중간값보다 큰 수가 들어갈 우선순위 큐(큰 큐)이다.

- 수가 들어올 때 작은 큐와 큰 큐에 번갈아가며 넣으면 된다. 단,  이 때 규칙이있다.

1. 중간값은 항상 작은 큐의 top()에 위치한다.
2. 작은 큐의 사이즈는 큰 큐의 사이즈와 같거나 1만큼만 차이나야한다.
3. 큰 큐 -> 내림차순 / 작은 큐 -> 오름차순 이어야한다.

- 그림과 같은 경우를 보면 4가 들어왔을 때 두 큐의 사이즈가 같으면 작은 큐에 우선으로 넣으면 된다. 그러면 자연스럽게 작은 큐의 top()이 중간값이 된다.

 

- 단, 고려해야하는 경우들이 있다. 예를 들어 위와 같은 상황에서 이번에는 9가 들어온다고 생각해보자

- 두 큐의 사이즈가 같다고 작은 큐에 넣으면 작은 큐의 top()이 9가 되어버린다. 따라서 이런경우 큰 큐의 top()인 5를 작은 큐에 push()하고 큰 큐를 pop()한 뒤 9를 큰 큐에 넣어주면된다. 이 때의 중간 값은 작은 큐의 top()인 5가 된다.

 

#include <iostream>
#include <queue>

using namespace std;
priority_queue<int, vector<int>, greater<int>> a; // mid보다 큰 값들
priority_queue<int> b;		// mid보다 작은 값들

void qinsert(int num)
{
	if (b.size() > a.size())
	{
		if (b.empty())
		{
			a.push(num);
		}
		else if (b.top() > num)
		{
			a.push(b.top());
			b.pop();
			b.push(num);
		}
		else
		{
			a.push(num);
		}
	}
	else
	{
		if (a.empty())
		{
			b.push(num);
		}
		else if (a.top() < num)
		{
			b.push(a.top());
			a.pop();
			a.push(num);
		}
		else
		{
			b.push(num);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N,num;
	cin >> N;
	int* arr = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> num;
		qinsert(num);
		cout << b.top() << '\n';
	}
	return 0;
}

 

 

문제 링크

- 가운데를 말해요_백준