[C++] 백준(BOJ) 1655 가운데를 말해요

- 문제

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

1655번: 가운데를 말해요

- 문제분석

쿼리형 문제로 매 쿼리마다 배열의 중간값을 찾고, 새로운 수를 삽입하는 문제이다.

문제의 조건 총쿼리의 수는 1 ≤ N ≤ 100,000이다.

 

O(N²) = 10¹⁰ (100억 => 시간 초과)

 

따라서 O(NlogN) 이하의 시간복잡도를 가져야 한다. 다시 말해 각 쿼리를 수행하는 알고리즘은 반드시 O(logN)을 만족해야 시간 초과를 피할 수 있다. 쿼리 내에서 수행하는 연산은 다음과 같다. 

1. 새로운 숫자 삽입
2. 중간값 갱신

나이브하게 배열의 모든 수를 순회(O(N))하여 중간값을 찾으면 안 되기 때문에 다른 방법을 생각해야 한다.

 

- 풀이

항상 중간값을 유지할 수 있는 자료구조를 생각해보자. 정렬된 배열은 항상 다음과 같은 구조를 가진다.

이러한 구조에서 중간값보다 작은 새로운 수를 삽입하면 아래와 같이 수의 이동이 발생한다.

 

1. 중간값보다 작은 수의 집합에서 가장 큰수가 중간값이 된다.
2. 기존의 중간값은 중간값보다 큰수의 집합으로 간다.

이를 위해선 Heap을 사용하여 각 집합에서 최대값, 최소값을 O(logN)이내에 수행해야한다. 

반대의 경우도 마찬가지이다.

- 코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int center;
priority_queue<int, vector<int>, greater<int>> rightPart;	// 중간값보다 큰 집합(minHeap)
priority_queue<int, vector<int>, less<int>> leftPart;		// 중간값보다 작은 집합(maxHeap)

void print_center() { cout << center << "\n"; }	// 중간값 출력
void insert(int num) {		
	// 새로운 수 추가하는 함수
	if (leftPart.size() == rightPart.size()) {
		if (rightPart.empty()) {
			rightPart.push(max(center, num));
			center = min(center, num);
		}
		else if (num < leftPart.top()) {
			rightPart.push(center);
			center = leftPart.top();
			leftPart.pop();
			leftPart.push(num);
		}
		else if (num <= center) {
			rightPart.push(center);
			center = num;
		}
		else {
			rightPart.push(num);
		}
	}
	else if (leftPart.size() < rightPart.size()) {
		if (num <= center) {
			leftPart.push(num);
		}
		else if (num < rightPart.top()) {
			leftPart.push(center);
			center = num;
		}
		else {
			leftPart.push(center);
			center = rightPart.top();
			rightPart.pop();
			rightPart.push(num);
		}
	}
}

int main() {
	fastio;

	int n; cin >> n;
	
	cin >> center;	// 첫번째 숫자는 바로 center
	print_center();	

	for (int i = 0; i < n - 1; i++) {
		int num; cin >> num;	// 1. 숫자 입력
		insert(num);		// 2. 자료구조에 insert
		print_center();		// 3. 중간값 출력
	}
}