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. priority_queue로 최대힙, 최소힙 둘 다 선언
2. 먼저 최대힙에 넣고, 다음 원소를 최소힙에 넣는 식으로 입력을 받음
3. 입력을 받을 때마다, 최대힙의 top과 최소힙의 top을 비교하여 최대힙의 top이 더 크면 교환함
4. 이후 최대힙의 top을 출력(이것이 중간값이니까)
원리
2~3 과정을 거치면서, 최대힙에는 작은 수들이 저장되고, 최소힙에는 큰 수들이 저장된다.
그리고 작은 수들의 최대는 중간값이다.
코드
#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"; }}