[힙] 11655번 가운데를 말해요

1. 문제

2. 나의 풀이

• 남의 풀이 이해하기
  
• 남의 풀이에 주석달기

import sys
import heapq

N = int(input())
left, right = [], []

# 중앙값을 기준으로 큰 값은 오른쪽, 작은값은 왼쪽에 저장
# left는 max_heap
# right는 min_heap
for _ in range(N):
    num = int(sys.stdin.readline())

    # 우선 순차적으로 left/right에 균등하게 반반 넣어줍니당
    if len(left) == len(right):
        # 왜 마이너스 num인가? max_heap으로 만들려고 (오름차순 정렬)
        heapq.heappush(left, (-num, num))
    else:
        # heap은 디폴트가 min_heap
        heapq.heappush(right, (num, num))

    # 넣고나서 오른쪽보다 작은 이 왼쪽에 넣어졌는지를 확인하죠
    if right and left[0][1] > right[0][1]:
        # right가 존재하고, left의 첫번째(min)보다 right의 첫번째 (max)가 클 때
        # left의 첫번째(min), right의 첫번째를 각 right와 left에 push 함
        left_value = heapq.heappop(left)[1]
        right_value = heapq.heappop(right)[1]
        heapq.heappush(right, (left_value, left_value))
        heapq.heappush(left, (-right_value, right_value))

    print(left[0][1])

3. 남의 풀이

https://inspirit941.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1655-%EA%B0%80%EC%9A%B4%EB%8D%B0%EB%A5%BC-%EB%A7%90%ED%95%B4%EC%9A%94

4. 느낀 점

• heapq는 디폴트가 min heap이다 (오름차순 정렬)
• 최대힙을 만드는 간단한 방법은!! heapq.heappush(heap, (-num, num)) 아주 신박함!