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

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

# 가운데를 말해요
import sys
import heapq
input = sys.stdin.readline

N = int(input())
left = []
right = []
for _ in range(N):
    if len(left) == len(right):
        heapq.heappush(left, -int(input()))
    else:
        heapq.heappush(right, int(input()))
    if len(left) != 0 and len(right) != 0 and -left[0] > right[0]:
        add_left = heapq.heappop(right)
        add_right = heapq.heappop(left)
        heapq.heappush(left, -add_left)
        heapq.heappush(right, -add_right)
    print(-left[0])

 

자료구조(힙)

left : 최대힙으로 왼쪽 트리에 해당, right: 최소힙으로 오른쪽 트리에 해당

1. 양쪽 힙에 번갈아가면서 데이터를 push를 하고

2. left에서 가장 큰값(0번)이 right에서 가장 작은값(0번)보다 크면 두 자리를 바꿔준다

3. left에서 가장 큰값(0번)을 출력해 준다

 

코드를 보지 않았지만 어떤방식으로 접근을 해야 시간초과가 안나올지 생각하다가

결국 아이디어를 보고 풀었다 모르면 어렵고 알면 쉬운 각박한 알고리즘 세상