[백준] 1655번 : 가운데를 말해요 (Python)

 문제는 간단하다. 숫자를 하나씩 받고 지금까지의 숫자들 중에서 중앙값을 답하면 된다. (단, 짝수의 경우 두 수 중에서 작은 값을 답해야 한다) 처음에는 정말 간단하게, sort()를 통해서 중앙값을 답하였으나, 역시나 시간 초과. 

 이를 해결하기 위해서는, 매번 중앙값을 찾기 위해서 sort()하는 과정을 생략해야 한다. 해결과정은 다음과 같다.

• 숫자 리스트를 두 가지로 나누어서 생각한다. 왼쪽에는 작은 값들이, 오른쪽에는 큰 값들이 들어간다.
• 왼쪽의 리스트에서 가장 큰 값은 중앙값이다.
• 위의 조건이 만족하도록 숫자를 입력한다.

 숫자는 왼쪽, 오른쪽 번갈아가며 채우며, 왼쪽에 오른쪽보다 큰 숫자가 들어가는 경우 두 숫자를 교환한다. 즉, 왼쪽의 가장 큰 값과 오른쪽의 가장 작은 값을 비교한다. 이를 위해서, 왼쪽은 가장 큰 값이 루트가 되도록 max_heap, 오른쪽은 가장 작은 값이 루트가 되도록 min_heap으로 사용한다. 풀이한 코드는 다음과 같다.  

import sys
import heapq

# Let's keep the value of left root is the answer
cnt = int(sys.stdin.readline())
left, right = [], [] 

for i in range(cnt):
  num = int(sys.stdin.readline())
  
  # Fill in the numbers from the left
  if len(left) == len(right):
    heapq.heappush(left, (-num, num))
  else:
    heapq.heappush(right, (num, num))

  # Compare if left is bigger than right 
  if i > 0 and left[0][1] > right[0][1]:
    temp_l = heapq.heappop(left)[1]
    temp_r = heapq.heappop(right)[1]
    heapq.heappush(left, (-temp_r, temp_r))
    heapq.heappush(right, (temp_l, temp_l))

  print(left[0][1])