1655번 (힙으로 가운데값 구하기)

1.문제

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

1655번: 가운데를 말해요

2.아이디어

처음 문제를 접했을 때 n개의 입력이 들어올때마다 정렬을 수행하고 정렬된 배열의 가운데값을 출력하는 코드를 작성했었다. 정렬을 하기위해 O(nlogn)의 시간복잡도가 걸리고 총 n번의 정렬을 수행해야 하므로

총 O(n * nlogn)의 시간복잡도가 걸리게되고 n = 100,000이므로 제한시간인 0.1초를 넘기게 되어 시간초과로 통과하지 못했다.

 

이후 구글링을 하여 여러 풀이를 참고한결과 힙을 통해 정렬을 수행하면 O(logn)만에 정렬을 할 수 있다는것을 알게되었고, 최대힙 + 최소힙 두가지 힙을 사용하여 가운데값을 구하는 알고리즘이 있음을 알게되어 이를 활용하여 문제를 해결하였다.

 

임의의 두 집합 A , B가 있다고 가정하자. 중간값을 찾기 위한 조건은 다음과 같다.

 

1. A의 모든 원소가 B의 모든 원소보다 작다

2. 1을 만족하고 A의 원소의 갯수가 B의 원소의 갯수와 같거나 한개 더 많을때 A의 최대값이 중간값이된다.

 

3.풀이

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, input;

	cin >> n;

	cin >> input;

	max_heap.push(input);

	cout << input << "\n";

	for (int i = 0; i < n-1; i++) {
		cin >> input;

		if (i % 2 == 0) { // 최소 힙에
			min_heap.push(input);
		}
		else { // 최대 힙에
			max_heap.push(input);
		}

		if (max_heap.top() > min_heap.top()) {
			int tmp = max_heap.top();
			max_heap.pop();
			max_heap.push(min_heap.top());
			min_heap.pop();
			min_heap.push(tmp);
		}

		cout << max_heap.top() << "\n";
	}

	return 0;
}

 

1번 조건을 만족하기 위해 처음에 들어오는 입력은 최대힙에 넣어주고, 이후에 들어오는 입력은 최소힙, 최대힙을 번갈아가며 넣어준다. 이를위해 i가 짝수인경우와 홀수인경우를 나눠서 번갈아 힙에 넣어주었다.

만약 최대힙의 root값보다 최소힙의 root값이 더 작은경우 1번 조건을 만족하지 못하게되므로 둘을 바꿔주는 코드를 넣어준다.