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

---

소스코드

import sys

import heapq

input = sys.stdin.readline

n = int(input())

max_h, min_h = [], []

for i in range(n):

    num = int(input())

    if len(max_h) == len(min_h):

        heapq.heappush(max_h, -num)

    else:

        heapq.heappush(min_h, num)

    if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0] * -1 > min_h[0]:

        max_value = heapq.heappop(max_h) * -1

        min_value = heapq.heappop(min_h)

        

        heapq.heappush(max_h, min_value * -1)

        heapq.heappush(min_h, max_value)

    print(max_h[0] * -1)

---

알고리즘

처음에 입력 받을때마다 정렬한 후 리스트[len(리스트)//2] 를 했는데 시간초과가 나왔다...

찾아보니 2개의 heap을 써서 풀어야하는 문제였다.

왼쪽은 최대힙, 오른쪽은 최소 힙으로 정렬을 해나가면 된다.

그리고 다음 알고리즘을 사용하면 되는데 최소 최대 힙을 만들기 위해 -1을 곱하는 것은 옛날에 배웠는데 또 까먹었다...

1. 왼쪽 힙과 오른쪽 힙의 길이가 같으면 (요소 * -1) 을 왼쪽 힙에 삽입한다.
   1-1. 그렇지 않으면 오른쪽 힙에 삽입한다.
2. 왼쪽 힙과 오른쪽 힙에 요소가 존재하고, 왼쪽 힙의 (첫번째 요소* -1) 가 오른쪽 첫번째 요소보다 클 때
   2-1. 왼쪽 힙의 첫번째 요소와 오른쪽 힙의 첫번째 요소를 바꿔준다. ( -1을 곱해준 뒤 바꿔준다. )
3. 왼쪽 힙의 (첫번째 요소 * -1)를 출력한다.

ex) [1, 5, 2, 10, -99, 7, 5]
1 -> left = [-1] / right = []
5 -> left = [-1], right = [5]
2 -> left = [-2,-1], right = [5]
10 -> left = [-2,-1], right = [5,10]
-99 -> left = [-2,-1,99], right = [5,10]
7 -> left = [-2,-1,99], right = [5,7,10]
5 -> left = [-5,-2,-1,99], right = [5,7,10]

 

이러면 왼쪽힙의 첫번째는 중간값이 된다.