가운데를 말해요 ( 1655 번 )

1655번: 가운데를 말해요

 

---

🧠 알고리즘

• 힙(Heap)을 활용한 실시간 중앙값(Median) 유지

 

✔️ 동작 방식

• 문제 핵심 아이디어
  • 최대 힙(l_hq)과 최소 힙(r_hq)을 사용하여 중앙값을 효율적으로 관리한다. 

1. 입력 숫자 num을 읽는다.
2. 두 힙의 크기를 비교
   • 크기가 같으면 최대 힙에 넣음 (중앙값 후보)
   • 크기가 다르면 최소 힙에 넣음
3. 힙 정리
   • 최대 힙의 루트값이 최소 힙의 루트값보다 큰 경우, 두 값을 교환하여 중앙값 유지
4. 중앙값 출력
   • 항상 최대 힙 루트가 현재까지의 중앙값이 됨

---

 

🧾 코드

import sys, heapq
# 최대 힙, 최소 힙
l_hq, r_hq = [], []

n = int(sys.stdin.readline().rstrip())
for _ in range(n):
    len_l, len_r = len(l_hq), len(r_hq)
    num = int(sys.stdin.readline().rstrip())

    if len_l == len_r:
        heapq.heappush(l_hq, num * -1)
    else:
        heapq.heappush(r_hq, num)

    while l_hq and r_hq and (l_hq[0] * (-1) > r_hq[0]):
        l_pop, r_pop = heapq.heappop(l_hq), heapq.heappop(r_hq)
        heapq.heappush(l_hq, r_pop * -1)
        heapq.heappush(r_hq, l_pop * -1)

    print(l_hq[0] * -1)

---

 

⏱️ 시간 복잡도

for _ in range(n) : 전체 숫자 처리 ( 선형 시간 )
    heapq : 힙 연산 ( 로그 시간 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )