[백준] 1655번 가운데를 말해요

문제 설명

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

제한 사항

-첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

​-한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

​

입출력 예

input	output
7 1 5 2 10 -99 7 5	1 1 2 2 2 2 5

​

접근법

두 개의 우선순위 큐를 생성해 줍니다. 왼쪽 큐는 최소힙 큐(오름차순)이고 오른쪽은 최대힙 큐(내림차순)로 만들어 주시면됩니다.(최소힙 큐는 우선순위를 입력 수의 -로 해주시면 됩니다.) 만약에 두 큐의 크기가 같으면 왼쪽 큐에 넣어주고, 아니라면 오른쪽 큐에 넣어줍니다. 그리고, 두 큐가 비어있지 않을 경우, 왼쪽 큐의 끝 값과, 오른쪽 큐의 끝 값을 비교해 보았을 때, 왼쪽 큐가 더 크다면 빼서 바꿔줍니다. 그리고 왼쪽 큐의 마지막 값을 빼서 mid리스트에 넣어주시면 됩니다.

​

나의 코드

import sys
import heapq

N = int(sys.stdin.readline())
left_heap = []
right_heap = []
mid_list = []
for _ in range(N):
    number = int(sys.stdin.readline())
    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap,(-number,number))
    else:
        heapq.heappush(right_heap,(number,number))
    if len(left_heap) != 0 and len(right_heap) != 0 and left_heap[0][1] > right_heap[0][1]:
            left_number = heapq.heappop(left_heap)[1]
            right_number = heapq.heappop(right_heap)[1]
            heapq.heappush(left_heap,(-right_number,right_number))
            heapq.heappush(right_heap, (left_number, left_number))
    mid_list.append(left_heap[0][1])

for mid in mid_list:
    sys.stdout.write(str(mid)+"\n")