[백준 1655] 가운데를 말해요

코린이

[백준 1655] 가운데를 말해요

남탓일상 2024. 10. 4. 15:29

SMALL

import heapq #큐(Heap)라이브러리
import sys #입력 빠르게 만듦
input = sys.stdin.readline

leftHeap = []   # 최대힙,중앙값보다 작은 값들
rightHeap = []  # 최소힙, 중앙값보다 큰 값들

case=int(input())
for i in range(case):
    number = int(input())
	#예시1
    if len(leftHeap) == len(rightHeap) : 
        heapq.heappush(leftHeap, -number)#최대힙으로 사용하려면 leftheap을 음수로 저장한다.
    else :
        heapq.heappush(rightHeap, number)
    #예시2
    if rightHeap and (-1 * leftHeap[0]) > rightHeap[0] :#leftHeap의 최대값과 rightHeap의 최소값비교하고 자리바꿈
        left = heapq.heappop(leftHeap)#예시3
        right = heapq.heappop(rightHeap)

        heapq.heappush(rightHeap, -left)
        heapq.heappush(leftHeap, -right)
    print(leftHeap[0]*-1)

입력: 1 5 2 10 -99 7 5

예시1 예시2 예시3

[ ] [ ] => [ ] [ ]

[-1] [ ] => [ ] [1] => [1]

[-1] [5] => [-1] [5] => [1]

[-2,-1] [5] => [-2,-1] [5] => [2]

[-2,-1] [5,10] => [-2,-1] [5,10] => [2]

[-2,-1,99] [5,10] => [-2,-1,99] [5,10] => [2]

[-2,-1,99] [5,7,10] => [-2,-1,99] [5,7,10] => [2]

[-5,-2,-1,99] [5,7,10] => [-5,-2,-1,99] [5,7,10] => [5]

아 자료구조때 열심히 할 걸 알고리즘도 열심히 할 걸 후회하고 후회해요~~ 그리고하나~~ 아프고아파도~~ 그래도 한번~~~

LIST