[백준] 1655번 가운데를 말해요 [C++]

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

1655번: 가운데를 말해요

---

문제

---

접근 방식

시간제한이 매우 짧아서 입력과 동시에 어떤 수를 출력할지를 정해야한다.

그러기 위해서 우선 하나는 오름차순으로,하나는 내림차순으로 두가지의 우선순위 큐를 만든다. 

그리고 숫자가 입력될 때마다 현재의 mid값과 비교해서 큐에 넣어주는데,

1. 입력된 숫자가 mid보다 작다면
2. 입력된 숫자가 mid보다 크거나 같다면

두가지로 나뉜다.

1 번일 경우에는 입력된 숫자를 내림차순으로 정렬한 큐에, 2 번일 경우에는 오름차순으로 정렬한 큐에 숫자를 넣는다.

그 후 큐의 사이즈를 비교하게 되는데, 만약에 오름차순 큐가 내림차순 큐보다 크다면, 오름차순 큐의 맨 앞이 mid가 되며 mid를 내림차순 큐에 집어넣으면 된다.

반대로 , 내림차순 큐가 오름차순 큐보다 1개보다 더 크게 된다면, 내림차순 큐의 맨 처음이 mid가 되며 mid를 오름차순 큐에 집어넣으면 된다.

---

코드

 

#include <iostream>
#include <algorithm>
#include <stack>
#include<queue>
#include<cmath>
using namespace std;
int n;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	priority_queue<int, vector<int>> pq1; //내림차순 큐
	priority_queue<int, vector<int>, greater<int>> pq2; //오름차순 큐
	cin >> n;
	int mid;
	int x;
	cin >> x;
	mid = x;
	cout << mid << '\n';
	for (int i = 1; i < n; i++) {	
		cin >> x;
		if (x < mid) {
			pq1.push(x);
		}
		else {
			pq2.push(x);
		}
		if (pq1.size() > pq2.size()) {
			pq2.push(mid);
			mid = pq1.top();
			pq1.pop();
		}
		else if (pq1.size() == pq2.size() - 2) {
			pq1.push(mid);
			mid = pq2.top();
			pq2.pop();
		}
		cout << mid << '\n';
	}
}

---

두가지 우선순위 큐를 잘 활용해야 하는 문제였다