[BOJ 2696] 중앙값 구하기 C++

 

2696번: 중앙값 구하기

 

 

문제풀이

 

이 문제는 우선순위 큐 2개를 이용해서 풀 수 있다.

기본적으로 우선순위 큐가 Heap 구조이므로 Max Heap과 Min Heap 두 개를 선언한다.

비교함수를 따로 정해주지 않으면 기본적으로 내림차순에 따라 정렬한다. (Max Heap)

 

// Min Heap
priority_queue<int, vector<int, int>, greater<int>> minheap;
// Max Heap
priority_queue<int> maxheap;

 

중간값을 찾아야 하므로 두 큐의 크기는 같아야 한다.

우선 입력 받은 정수를 두 큐의 크기가 같도록 큐에 넣어준다.

 

그 후 max heap의 top과 min heap의 top을 비교했을 때 min heap의 top이 더 크다면

정렬이 제대로 되지 않은 상태이므로 max heap과 min heap의 top을 swap해준다.

 

maxheap의 top이 중앙값이므로 홀수번째 수를 읽을 때마다 maxheap의 top을 저장해주면 된다.

 

 

C++ 코드