가운데를 말해요

예제 입출력

코드

#include <stdio.h>
#include <queue>
using namespace std;

int main() {
	int n, a;
	scanf("%d", &n);
	priority_queue<int> max;	// 작은 수들 내림차순
	priority_queue<int, vector<int>, greater<int>> min;	// 큰 수들 오름차순
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		if (max.size() == min.size()) max.push(a);
		else min.push(a);
		if (!max.empty() && !min.empty() && max.top() > min.top()) {
			min.push(max.top());
			max.push(min.top());
			min.pop();
			max.pop();
		}
		printf("%d\n", max.top());
	}
	return 0;
}

시간제한(0.1초)로 인해 우선순위 큐로 작은 수 / 큰 수를 나눠서 풀어야한다..
그런 줄도 모르고 이분 탐색으로 붙잡고 있어서 계속 시간 초과가 났다😢

이분 탐색 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int n, a;
	scanf("%d", &n);
	scanf("%d", &a);
	vector<int> v;
	v.emplace_back(a);
	printf("%d\n", a);
	for (int i = 1; i < n; i++) {
		scanf("%d", &a);
		int left = 0, right = v.size() - 1, mid = (left + right) / 2;
		while (left < right) {		
			if (a < v[mid]) {
				right = mid - 1;
			}
			else if (a > v[mid]) {
				left = mid + 1;
			}
			else break;
			mid = (left + right) / 2;
		}

		if (a <= v[mid]) v.insert(v.begin() + mid, a);
		else v.insert(v.begin() + mid + 1, a);
		if (v.size() % 2 == 0) printf("%d\n",v[v.size() / 2 - 1]);
		else printf("%d\n", (v[v.size() / 2]));
	}
	return 0;
}

시간 초과의 원인을 해결해보겠다며 cin -> scanf, cout -> printf로도 고쳐봤다.. 별로 효과가 없음을 알면서도...