1655 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

접근 방식이 헷갈려서 찾아본 문제이다.

우선, 문제의 조건부터 살펴보자. 가운데의 인덱스를 구하기 위해선 정렬이 어떤 형태로든, 무조건 되어 있어야 한다.

또한 시간 제한이 0.1초로 고정되어 있기 때문에, NlogN의 정렬을 사용하면 시간 초과가 발생한다.

따라서 다른 정렬 방식을 사용해야 한다.

 

고려해 볼 수 있는 자료구조로 우선순위 큐를 볼 수 있다. 우선순위 큐는 logN의 복잡도를 가지기 때문에, N = 10만이어도 제한을 만족할만 하다.

 

편의상 중앙 값을 기준으로 왼쪽 배열은 left_subarray, 오른쪽 배열은 right_subarray라 칭하겠다. 

1. 중앙값을 기준으로 left_subarray는 최대 힙으로 관리한다.

2. 중앙값을 기준으로 right_subarray는 최소 힙으로 관리한다.

왜 ? 우리의 목적은 중앙값을 찾는 것이기 때문에 중앙의 인덱스를 계산하기 편리하도록 큐의 원소를 넣고 빼는 작업을 사용한다.

 

그런데 주의해야 할 사항은 N이 짝수일 때, 중앙값은 (N / 2) -1이기 때문에, 크기가 left_subarray + 1 == right_subarray가 될 수도 있다. 이 조건에 유의하면 된다.

 

정답코드

#include <iostream>
#include <queue>
#include <functional>
using namespace std;
int N;
priority_queue<int> maxq;
priority_queue<int, vector<int>, greater<int>> minq;
int main()
{
	cin >> N;
	int num, mid = 0, cnt = 0;
	scanf("%d", &num);
	mid = num;
	printf("%d\n", mid);
	for (int i = 1; i < N; i++) {
		scanf("%d", &num);
		cnt++;
		if (mid <= num) {
			minq.push(num);
		}
		else {
			maxq.push(num);
		}
		int size = maxq.size();

		if (size != minq.size() && size + 1 != minq.size()) {
			if (maxq.size() > minq.size()) {
				minq.push(mid);
				mid = maxq.top();
				maxq.pop();
			}
			else {
				maxq.push(mid);
				mid = minq.top();
				minq.pop();
			}
		}
		printf("%d\n", mid);
	}
	return 0;
}