알고리즘/백준
[백준 2696] 중앙값 구하기 (C++)
라이언납시오
2021. 8. 20. 18:22
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/2696
2696번: 중앙값 구하기
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주
www.acmicpc.net
1. 주의할 점
- 홀수번째마다 정렬해서 중앙값을 구하지 않는다
2. 구현
- 2가지의 우선순위 큐를 사용한다(오름차순 정렬, 내림차순 정렬 각각 1개씩)
- 중앙값을 기준으로 왼쪽에는 내림차순으로 정렬된 Left 우선순위큐를, 오른쪽에는 오름차순으로 정렬된 Right 우선순위큐가 있다고 가정한다
- 홀수번째마다 Right와 Left의 크기를 비교하며 만약 한쪽으로 치우쳐진 경우, 옆으로 1개씩 밀어낸다(아래 TC를 통해 원리를 이해하자)
더보기
TC #1
1
3
1 7 10
i=0)
Median: 1, Left: Empty, Right: Empty
i=1)
Median: 1, Left: Empty, Right: 7
i=2)
Median: 1, Left: Empty, Right: 7 10
위의 경우, i=2일때 치우쳐져있으므로 Median을 Left로, Right의 Top을 Median으로 민다
이후 상태
Median: 7, Left: 1, Right: 10
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int test, num, val, median;
cin >> test;
for (int t = 0; t < test; t++) {
priority_queue<long long, vector<long long>, less<long long>> left; //중앙값>= 를 만족하는 수
priority_queue<long long, vector<long long>, greater<long long>> right; //중앙값<= 를 만족하는 수
vector<int> v;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> val;
if (i == 0) median = val;
else {
if (val <= median) left.push(val);
else right.push(val);
}
if (i % 2 == 0) {
if (left.size() > right.size()) {
right.push(median);
median = left.top();
left.pop();
}
else if (left.size() < right.size()) {
left.push(median);
median = right.top();
right.pop();
}
v.push_back(median);
}
}
cout << num / 2 + 1 << '\n';
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
if ((i+1) % 10 == 0) cout << '\n';
}
cout << '\n';
}
return 0;
}
728x90
반응형