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

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

처음에 문제를 이해하는데도 시간이 걸렸다..

결국 SORTING 해서 중간에 있는 값을 찾아야 하는건데,

입력값이 계속 들어올 때 마다 SORTING 을 해 주어야 알 수 있을 것 같다.

 

그래서 처음에는 입력값을 받을때마다 sort 를 했는데 역시나 시간초과..

 

아마 내가 모르는 모듈을 써야 할 것 같아서 찾아봤는데

heap 을 사용해서 코딩을 짜야 하는 것이었다.

 

사실 그동안 heap 이라는걸 들어만 보고 구체적으로 어떻게 사용하는 건줄 몰랐는데,

생각보다 매우 간편하고, 이런 sorting 문제에 활용 하면 좋을 것 같다.

 

728x90

from sys import stdin
import heapq
input=stdin.readline
T=int(input())
left=[]
right=[]
ans=[]
for i in range(T):
    Num=int(input())
    if len(left)==len(right):
        heapq.heappush(left,(-Num,Num))
    else:
        heapq.heappush(right,(Num,Num))
    if right and left[0][1]>right[0][0]:
        mn=heapq.heappop(right)[0]
        mx=heapq.heappop(left)[1]
        heapq.heappush(left,(-mn,mn))
        heapq.heappush(right,(mx,mx))
        
    ans.append(left[0][1])

for i in range(T):
    print(ans[i])

그래서 읽다보니.. 왜 튜플로 삽입하는지 몰랏는데, 최대 힙을 설정하기 위한거였다.

 

(left) . . . . . . (right)

(-1,1)               (6,6)

(-2,2)               (5,5)

(-3,3) .... root ..... (4,4)

 

쉽게 말해서, Left에는 root로 갈 수록 제일 큰 값이어야 하기 때문에, root 값에 최소값이 들어가게 되면 안된다.

그래서 튜플값으로(-값,값)으로 넣어주는데 튜플로 넣는 경우 첫번째 값으로 root 값이 변하기 때문이다.

큰 값에 (-)를 붙이면 그만큼 작아지기 때문에 정렬이 된다고 생각하면 된다.

다만, right은 기존대로 제일 작은 값이 root 값으로 들어와야 하기 때문에(값,값)으로 넣어준다.

 

그런데, left 의 root 가 중간값이어야 하기 때문에, left의 root 가 right 의 root값보다 크다면 서로 바꿔준다.

그리고 pop으로 불러올때는 인덱스[1]값을 불러오면 되기 때문에 문제 없다.