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

 

 

 

---

 

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]

 

---

 

 

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