수가 하나씩 주어질 때마다 지금까지 주어진 수 중 중간값을 출력하는 문제입니다. 이 문제는 우선순위 큐를 사용하는데, 여기서 생각할 점은 우선순위 큐의 top에 어떻게 중간값을 가져오는가입니다. 사실 이건 생각을 한 번만 비틀면 떠올릴 수 있는데, 바로 지금까지 주어진 수를 작은 쪽 반을 max heap에, 큰 쪽 반을 min heap에 저장하는 방법입니다. 일단 원소가 들어올 때마다 작은 쪽 반을 저장하는 max heap에 넣고, max heap의 top을 min heap에 push 한 후 다시 min heap의 top을 max heap에 push합니다. 이렇게 하면 새로운 원소가 들어올 때 min heap의 top보다 크다면 min heap의 top이, 그렇지 않다면 max heap에 그대로 남게 됩니다. 그리고나서 max heap의 크기를 min heap의 크기와 같거나 1 크게 유지하면 max heap의 top에 항상 중간값이 오게 됩니다.
PS알못 OrbitHv의 PS