2696번: 중앙값 구하기 
문제 링크: 2696번: 중앙값 구하기
개요
문제가 시킨 일인 수열이 주어지면 홀수 번째 수를 읽을 때마다 중앙값을 출력하는 작업만 착실하게 수행하면 되는 문제이다. 하지만 매번 수열을 정렬하고 중간 인덱스 값을 출력하는 방식으로는 시간초과를 피할 수 없다. 따라서 우선순위 큐를 두 개 이용해서 풀이할 것이다.
maxPq와 minPq를 이용할 것이다. maxPq에선 값이 큰 수가 높은 우선순위를, minPq에선 값이 작은 수가 높은 우선순위를 갖게 했다. maxPq엔 중앙값과 중앙값보다 작은 수들이, minPq에는 중앙값보다 큰 수들이 존재하도록 유지할 것이다. (중앙값이 중복일 경우 minPq에 중앙값과 같은 수가 존재할 수도 있다.)
풀이
우선순위 큐에 수 입력
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if (maxPq.size() == minPq.size()) { //홀수 번째 입력할 차례
if (maxPq.empty() || minPq.top() >= num) {
maxPq.push(num);
}
else {
maxPq.push(minPq.top());
minPq.pop();
minPq.push(num);
}
}
else { //짝수 번째 입력할 차례
if (maxPq.top() > num) {
minPq.push(maxPq.top());
maxPq.pop();
maxPq.push(num);
}
else {
minPq.push(num);
}
}
우선 maxPq와 minPq에 있는 수들의 개수 동일 여부를 이용해서 분기를 나누었다. maxPq.size() == minPq.size()인 경우엔 총 숫자가 짝수개 존재하므로 홀수 번째 수를 입력할 차례이고, 그렇지 않다면 짝수 번째 수를 입력할 차례이다.
1. 홀수 번째 입력할 차례
이번 수가 minPq.top()보다 작거나 같은 경우엔 고민없이 maxPq에 push해주면 된다.
조건에 minPq.top() 대신 maxPq.top()을 사용하면 이번 수가 중앙값이 될 경우가 반례가 된다. 이번 수가 minPq.top()보다 큰 경우엔 조금 귀찮다. 이번 수가 입력된 후에는 maxPq의 크기가 minPq보다 딱 1 큰 상태로 유지되게 해야 하므로 우선 minPq.top()을 maxPq로 이동시켜준 후, 이번 수를 minPq에 push해줘야 한다.
2. 짝수 번째 입력할 차례
이번 수가 maxPq.top()보다 작은 경우엔 또다시 귀찮다. 이번 수가 입력된 후에는 maxPq의 크기와 minPq의 크기가 같도록 유지시켜줘야 하므로 우선 maxPq.top()을 minPq로 이동시켜준 후, 이번 수를 maxPq에 push해줘야 한다.
그렇지 않은 경우엔 그냥 minPq에 push해주면 된다.
중앙값 저장
1
2
3
if (i % 2 == 0) {
mid[midIdx++] = maxPq.top();
}
홀수 번째 수를 입력받으면 우선순위 큐에 저장한 뒤에 별도 배열에 중앙값(maxPq.top())을 순서대로 저장해준다. 이후 입력이 종료되면 순서대로 출력해주면 된다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <queue>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_M 9999
int main() {
int t;
scanf("%d", &t);
while (t--) {
priority_queue<int> maxPq;
priority_queue<int, vector<int>, greater<int> > minPq;
int n, mid[MAX_M], midIdx = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
if (maxPq.size() == minPq.size()) { //홀수 번째 입력할 차례
if (maxPq.empty() || minPq.top() >= num) {
maxPq.push(num);
}
else {
maxPq.push(minPq.top());
minPq.pop();
minPq.push(num);
}
}
else { //짝수 번째 입력할 차례
if (maxPq.top() > num) {
minPq.push(maxPq.top());
maxPq.pop();
maxPq.push(num);
}
else {
minPq.push(num);
}
}
if (i % 2 == 0) {
mid[midIdx++] = maxPq.top();
}
}
printf("%d", midIdx);
for (int i = 0; i < midIdx; i++) {
if (i % 10 == 0) printf("\n");
printf("%d ", mid[i]);
}
printf("\n");
}
return 0;
}