궤도

문제 풀이 이 문제의 시간 제한은 0.1초다. 그니까 입력이 들어오자마자 바로바로 출력을 내보내야 한다는 것이다. 입력을 받을 때를 제외하곤 단 하나의 for문도 쓸 수 없다. 그럼 도대체 제일 작은 값도 제일 큰 값도 아닌 중앙값을 바로바로 내보낼 것인가... 중앙값을 기준으로 그보다 작은 수는 최대 힙에 넣고 그보다 큰 수는 최소 힙에 넣는 것이다. 그렇다면 최대 힙의 top에는 중앙값보다 같거나 작은 수 중 가장 큰 수가, 최소 힙의 top에는 중앙값보다 같거나 큰 수 중 가장 작은 수가 올 것이다. 균형을 이루기 위해선 최대 힙과 최소 합의 원소의 갯수 차이가 0(원소의 총 갯수가 홀수)이거나 1(원소의 총 갯수가 짝수)이여야 한다. 만약 이 균형이 깨진다면 중앙값을 수정해야 한다. 위 상태에서 ..