1655: 가운데를 말해요

풀이 시간

• 34m
• 질문게시판을 보고 반례를 찾았다

구현 방식

• 가운데수 보다 작은 값들이 최대힙에 들어가고, 가운데수 보다 큰 값들이 최소힙에 들어가도록 해줘야한다
  -> N만틈 for문을 돌면서 두 힙의 길이를 맞춰가면서 값을 넣어주었다

• 그러나 이렇게만 처리해줄 경우, 오른쪽 힙에 왼쪽 힙보다 작은 값을 넣는 경우가 생긴다. 이 부분이 내가 고려하지 못했던 반례였다

• 따라서 두 힙의 길이를 맞춰가면서 값을 넣어주되, 왼쪽 힙의 head의 원소(-max_heap[0])와 오른쪽 힙의 head의 원소(min_heap[0])의 크기를 비교하여 만약 -max_heap[0]이 더 크다면 이 둘을 교체하여 다시 넣어주는 부분을 추가해주었다

코드

import sys
import heapq

N = int(sys.stdin.readline()[:-1])
max_heap = [] #중간값보다 작은 값들이 들어감 (가장 큰 값이 가운데이도록 유지)
min_heap = [] #중간값보다 큰 값들이 들어감 (가장 작은 값이 가운데이도록 유지)

for _ in range(N):
    new = int(sys.stdin.readline()[:-1])
    
    if len(max_heap) == len(min_heap):
        heapq.heappush(max_heap, -new)
    else:
        heapq.heappush(min_heap, new)
    
    if min_heap:
        if -max_heap[0] > min_heap[0]:
            low = -heapq.heappop(max_heap); high = heapq.heappop(min_heap)
            heapq.heappush(max_heap, -high)
            heapq.heappush(min_heap, low)

    print(-max_heap[0])

결과