1655 가운데를 말해요
내 방식 (multiset)
1
2
3
4
5
6
7
1. 멀티셋으로 가운데를 트래킹해가면서 구함
2. 첫번째 원소를 넣고, s.begin()으로 첫번째 iter를 middle로 받고 그대로 출력
3. 두번째부턴 middle과 같은 원소가 들어오면, s.insert(s.upperbound(*middle), input) 으로 가장 앞에 넣음
아니면 그냥 s.insert 로 넣음
4. 현재 넣는 것이 짝수번째 숫자이고, 넣은 원소가 현재 middle보다 작을 경우 middle-- (작은 원소가 들어왔을 때, middle은 반쪽 바로 앞에 위치하기에)
현재 넣는 것이 홀수번째 숫자이고, 넣은 원소가 현재 middle보다 같거나 클 경우 middle++ (같거나 큰 원소가 들어왔을 때, middle은 반쪽 바로 뒤에 위치하기에)
5. middle을 출력
정석 (우선순위 큐, 최대 힙, 최소힙)
1
2
3
4
5
6
7
8
9
1. priority_queue로 최대힙, 최소힙 둘 다 선언
2. 먼저 최대힙에 넣고, 다음 원소를 최소힙에 넣는 식으로 입력을 받음
3. 입력을 받을 때마다, 최대힙의 top과 최소힙의 top을 비교하여 최대힙의 top이 더 크면 교환함
4. 이후 최대힙의 top을 출력(이것이 중간값이니까)
원리
2~3 과정을 거치면서, 최대힙에는 작은 수들이 저장되고, 최소힙에는 큰 수들이 저장된다.
그리고 작은 수들의 최대는 중간값이다.
코드
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
#include <iostream>
#include <set>
using namespace std;
multiset<int> s;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int numOfN, temp;
cin >> numOfN >> temp;
s.insert(temp);
multiset<int>::iterator middle = s.begin();
cout << "result : " << *middle << "\n";
for (int i = 2; i <= numOfN; i++) {
cin >> temp;
int cur = *middle;
if (temp == cur)
s.insert(s.upper_bound(temp), temp);
else
s.insert(temp);
if (i % 2 == 1) {
if (temp >= cur)
middle++;
}
else if (i % 2 == 0) {
if (temp < cur)
middle--;
}
cout << "result : " << *middle << "\n";
for (multiset<int>::iterator iter = s.begin(); iter != s.end(); iter++)
cout << *iter << " ";
cout << "\n\n";
}
}