• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

문제: 가운데를 말해요

  • 값이 들어올 때마다 중간값을 실시간으로 계산해줘야하는 문제입니다.
  • 최대힙과 최소힙을 사용하여 더 빠르게 중간값을 구할 수 있습니다.

규칙

아래 세 개의 규칙을 유지하며 데이터를 넣으면 최대 힙의 top 값이 중간값이 됩니다.

  1. 최대 힙의 크기가 최소힙의 크기보다 1 크거나 같도록 유지하며 값을 넣습니다.
    • 두 힙의 크기가 같다면 최대힙부터 값을 넣습니다.
  2. 최소 힙에 있는 값은 모두, 최대 힙에 있는 값보다 큽니다.
  3. 값을 넣은 후에 최소 힙 top 값이 최대 힙 top 값보다 작다면 서로 값을 교환해줍니다.