[1655] 가운데를 말해요 (골드 2)

1655번: 가운데를 말해요

숫자가 연속되서 주어질 때, 가운데 숫자를 출력하는 문제이다.

고려했던 사항들은 다음과 같다.

• 제한시간이 파이썬의 경우 0.6초(타 언어의 경우 0.1초)이다.
• 주어진 수가 짝수개일 경우 가운데 2개중 작은걸 출력한다.

풀이 과정은 다음과 같다.

• heap2개를 준비한다.(smallHeap, bigHeap)
  • smallHeap(최대 힙), bigHeap(최소힙)으로 구성한다.
• 두 heap의 크기를 일정하도록 맞춰서 삽입한다.
  • heap의 크기다 같으면 small에 먼저 넣고, big으로 넣는다.
    • 홀수 개일 경우(heap의 크기가 같다면 새로 넣는 시점에) small의 root가 중간 값으로 출력시 통일감을 준다.
    • 짝수 개일 경우(heap의 크기가 다르다면 새로 넣는 시점에) small의 root가 중간 값으로 출력시 통일감을 준다.
• heap의 root를 비교해서 작은 값을 smllHeap의 root가 되도록 한다.
  • 출력시 smallRoot의 root를 출력하므로 맞추어 준다.

이 문제는 혼자서 못 풀어서 검색을 했다. 처음에는 1개의 heap을 사용하고 복사해서 절반을 빼는 방식으로 진행했지만 시간 초과가 났다[O(nlogn)]. 두번째 시도는 bisect를 사용해서 중간에 넣어주고(sort를 하면서 효과적으로 넣어주기 위함) 중간 인덱스를 출력하려 했지만 시간 초과가 났다[O(nlogn)]. heap 2개를 사용하는건 생각도 못해봤다...[O(nlogn)]
→ 빅오 표기법에서는 동일하지만, 제한 시간이 적은 만큼 복사의 유무, 빅오 표기법 안에 생략된 상수도 영향을 끼쳤다.

import sys
import heapq

n = int(sys.stdin.readline())
smallHeap, bigHeap = [], []
for _ in range(n):
  number = int(sys.stdin.readline())
  if len(smallHeap) == len(bigHeap):
    heapq.heappush(smallHeap, (-number, number))
  else:
    heapq.heappush(bigHeap, (number, number))
  if bigHeap and smallHeap[0][1] > bigHeap[0][1]:
    smallRoot = heapq.heappop(smallHeap)[1]
    bigRoot = heapq.heappop(bigHeap)[1]
    heapq.heappush(smallHeap, (-bigRoot, bigRoot))
    heapq.heappush(bigHeap, (smallRoot, smallRoot))
  print(smallHeap[0][1])

참고

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