Baekjoon / 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

리스트 정렬(sort)해서 가운데 값 return 하는 방식으로는 시간 초과 

heap 자료구조 방식 활용

 

Solution 

import heapq
import sys
input = sys.stdin.readline

n = int(input())
l_heap = []
r_heap = []

for _ in range(n) :
    num = int(input())
    if len(l_heap) == len(r_heap):
        heapq.heappush(l_heap,-num)
    else:
        heapq.heappush(r_heap,num)

    if len(l_heap)>=1 and len(r_heap)>=1 and l_heap[0]*(-1)>r_heap[0]:
        max_num = heapq.heappop(l_heap)*(-1)
        min_num = heapq.heappop(r_heap)

        heapq.heappush(l_heap, min_num*(-1))
        heapq.heappush(r_heap, max_num)

    print(l_heap[0]*(-1))
    # print('left : ', leftHeap, '/', 'right :', rightHeap)

(1) 양쪽 heap 개수 동일하면, Left heap 에 (-)형태로 넣는다

(2) 동일하지 않는 경우, Right heap 으로

(3) 만약 Left heap 제일 큰 수가 Right heap 제일 작은 수 보다 클 경우,

    Left heap 에서 빼서 (-1) 곱해준 후, Right heap 으로

    Right heap 에서도 제일 작은 값 빼서 (-1) 곱해준 후, Left heap으로 넣는다.

(4) 마지막으로, Left heap에서 제일 큰 수 출력

 

짝수 개수일 때나 홀수 개수일 때도, Left heap에 포함되어 있는 수 출력하기 때문에.