[Baekjoon] 1655. 가운데를 말해요

🔗 Problem Link

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

---

❔Thinking

• N개의 수가 차례대로 주어질 때, 현재까지 숫자들의 중앙값을 출력한다.
• 각 숫자는 -10,000이상 10,000이하의 정수이다.

---

💻Solution

import sys
import heapq
input = sys.stdin.readline

max_heap = []
min_heap = []
N = int(input().rstrip())
for _ in range(N):
    num = int(input().rstrip())
    heapq.heappush(max_heap, -num)

    if max_heap and min_heap and (-max_heap[0] > min_heap[0]):
        heapq.heappush(min_heap, -heapq.heappop(max_heap))

    if len(max_heap) > len(min_heap)+1:
        heapq.heappush(min_heap, -heapq.heappop(max_heap))
    elif len(max_heap) < len(min_heap):
        heapq.heappush(max_heap, -heapq.heappop(min_heap))
    
    if len(max_heap) == len(min_heap):
        print(min(-max_heap[0], min_heap[0]))
    else:
        print(-max_heap[0])

---

🗝️keypoint

1. 매번 정렬로 중앙값을 찾을 수 있으나, 문제 조건에 제한 시간이 0.1초이기 때문에 다른 방법을 생각해야 한다.
2. 최소힙과 최대힙을 사용하여 반으로 나뉜 배열을 구현하고, 그 사이의 값이 중앙값이 된다.

[자료구조] Priority Queue