[백준] 1655 가운데를 말해요 / 파이썬 (Python)

문제 링크 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

thinking

진짜 모르겠어서 답 보고 했다. 백준아 그 게임 하지마요.
사실 예제 출력에 대해서 아직 이해 못함...
heap씨가 다 해줄뿐...
해당 문제는 결국 정렬된 배열에서 중앙값을 구하는 문제인데, 시간 제한이 있어 힙을 사용해야한다.
중앙값을 구하기 위해서는 2개 힙으로 나누어 사용하는데,
최대힙에 1개의 값을 더 넣어 최대힙의 최대값이 중앙값이 되도록 하면 된다.
처음에는 이해가지 않았는데 그림을 그리다 보니 이해가 됐다.

 

max_heap의 최대값이 10, min_heap 최소값이 9라면 오름차순에 맞지 않기때문에 두 값을 교환해야한다.
이를 잘 알고 조건문을 써주면 된다!
 

import heapq, sys
n = int(sys.stdin.readline())
left_heap = []
right_heap = []
result = []

for i in range(n):
    num = int(sys.stdin.readline())
# left = 최대힙 / right = 최소힙
# left_heap이 right_heap보다 요소가 1개 더 많아야 함
    if len(left_heap) == len(right_heap): 
        heapq.heappush(left_heap, (-num, num))
    else:
        heapq.heappush(right_heap, num)

    if right_heap and left_heap[0][1] > right_heap[0]:
        left_value = heapq.heappop(left_heap)[1] # (0, 1) pop
        right_value = heapq.heappop(right_heap)
        heapq.heappush(left_heap, (-right_value, right_value))
        heapq.heappush(right_heap, left_value)

    result.append(left_heap[0][1])

for i in result:
    print(i)

파이썬 heapq는 최소힙이 기본 값이기 때문에 최대힙은 -1을 곱하여 사용하므로
left_heap에 (-num, num)을 push하고, right_heap과 교환할때 heapq.heappop(left_heap)[1]를 뽑아주면 된다!