수열에서 중앙값을 최적으로 구하는 알고리즘(백준 1655번)

문제 출처

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

1655번: 가운데를 말해요

중간값 구하기 알고리즘은 다음과 같다.

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.

2. 최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다.

이때 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값을 swap해준다.

[결과] 이때 이 두가지 규칙을 유지해 준다면 항상 최대 힙 top값이 중간값이 된다.

 

예시 그림을 통해 어떻게 구현을 하는지 알아보자.

1,2,3,4,5를 순서대로 넣을 때 중간값이 어떻게 구성되나 확인해본다.

처음에는 무조건 최대 힙에 값을 넣어준다. 왜냐면 최소 힙에 넣는 순간 (1)번 규칙에 어긋나게 된다.

이때 중간 값은 값 자체가 1개 뿐이니 1이다.

2를 넣을 때는 최대 힙에 넣는 순간 (1)규칙에 어긋나게 되므로 최소 힙에 넣는다.

그리고 (2)번 규칙에서 최대 힙의 최댓값이 최소 힙의 최솟값 보다 작거나 같으므로 swap하지 않는다.

이때 중간값은 1이다. 

(1)번 규칙에 의해 3은 최대 힙에 들어갔지만, (2)번 규칙에 현재 어긋난다.

따라서 3과 2를 swap해준다.

swap된 결과로 중간값이 1->3(아주잠깐)->2로 변하였다.

(1)번 규칙에 의해 최소 힙에 4를 넣어준다.

5를 넣을 때는 (1)번 규칙에 의해 5를 최대 힙에 넣어준다.

이때 최대 힙의 top 값은 5, 최소 힙의 top 값은 3이므로 (2) 규칙에 위배된다. 따라서 swap

결과적으로 1,1,2,2,3이라는 중간값이 생기게 된다.

1 :: 1

1, 2 :: 1

1, 2, 3 :: 2

1, 2, 3, 4 :: 2

1, 2, 3, 4, 5 :: 3

 

소스 코드(맞았어요!!) 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n; 
vector<int> v;

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

int main() {

cin >> n;
int temp; // -10,000 ~ +10,000
for (int x = 1; x <= n; x++) {

cin >> temp;
v.push_back(temp);
}

int middle_value;
int max_top;
int min_top;
for (int x = 0; x < (int)v.size(); x++) {

if (max_heap.empty())
max_heap.push(v[x]);

else if (max_heap.size() - min_heap.size() == 0)
max_heap.push(v[x]);

else 
min_heap.push(v[x]);

if (!max_heap.empty() && !min_heap.empty() && max_heap.top() > min_heap.top())
{
max_top = min_heap.top();
min_top = max_heap.top();

max_heap.pop();
min_heap.pop();

max_heap.push(max_top);
min_heap.push(min_top);

}

middle_value = max_heap.top();
cout << middle_value << "\n";
}
return 0;
}

소스 코드(시간 초과)

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int n; // 1 ~ 100,000
vector<int> v;
vector<int> m;

int binary(int right, int target);

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin >> n;
int temp; // -10,000 ~ +10,000

for (int x = 1; x <= n; x++) {

cin >> temp;
v.push_back(temp);
m.push_back(temp);
}

sort(v.begin(), v.end());

int middle;
int index;
for (int x = n-1; x >= 0; x--) {

middle = (v.size()-1) / 2;

index = binary(v.size()-1, m[x]); // bool을 반환. 

m[x] = v[middle];

v.erase(v.begin()+index, v.begin()+index+1);
}

for (int i : m)
cout << i << "\n";
return 0;
}

int binary(int right, int target) {

int left = 0;

int middle;

while (left <= right) {

middle = (left + right) / 2;

if (v[middle] == target)
return middle;

else if (v[middle] < target)
left = middle + 1;

else if (v[middle] > target)
right = middle - 1;

}
}