[Python] 1655번 : 가운데를 말해요 (max heap, min heap)

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

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줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

---

# https://www.acmicpc.net/problem/1655 
# 가운데를 말해요
 
import sys
import heapq
 
N = int(sys.stdin.readline())
 
# Heap을 2개 사용한다
 
left_heap = []  # Max heap 
right_heap = [] # Min heap
mid_value = []  # Mid value
 
for i in range(N):
    
    num = int(sys.stdin.readline())
 
    if (len(left_heap) == len(right_heap)):     # left heap과 right heap의 길이가 같을 경우
        tmp_n = num * (-1)                      # 입력값에 -1을 곱한다. (Max heap 부분, heapq 모듈을 이용하여 min heap을 max heap으로 구현)
        heapq.heappush(left_heap, tmp_n)        # heap을 이용하는 트리 연산 처리 모듈
        if (right_heap and ((left_heap[0])*(-1)) > right_heap[0]): # left heap의 root값이 right heap의 root 보다 클 경우 (단 right heap 값이 있어야함)
                                                                   # ㄴ 중간값을 기준으로 left heap은 중간값 보다 작아야 하기때문
            tmp_r = heapq.heappop(right_heap)   # right heap의 root 값을 pop 하고 임시값에 대입                   
            tmp_l = heapq.heappop(left_heap)    # left heap의 root 값을 pop 하고 임시값에 대입     
            heapq.heappush(left_heap, (tmp_r)*(-1))  # 조건문에 해당하면, right heap의 root 값에 -1을 곱하고 left heap으로 트리 연산 삽입
            heapq.heappush(right_heap, (tmp_l)*(-1)) # 조건문에 해당하면, left heap의 root 값에 -1을 곱하고 right heap으로 트리 연산 삽입
    
    else:  # left heap과 right heap의 길이기 같지 않은 경우
        heapq.heappush(right_heap, num) # right heap에 트리 연산 삽입
        if (((left_heap[0])*(-1)) > right_heap[0]):  # left heap의 root값이 right heap의 root 보다 클 경우
            tmp_r = heapq.heappop(right_heap)        # right heap의 root 값을 pop 하고 임시값에 대입
            tmp_l = heapq.heappop(left_heap)         # left heap의 root 값을 pop 하고 임시값에 대입
            heapq.heappush(left_heap, (tmp_r)*(-1))  # 조건문에 해당하면, right heap의 root 값에 -1을 곱하고 left heap으로 트리 연산 삽입 
            heapq.heappush(right_heap, (tmp_l)*(-1)) # 조건문에 해당하면, left heap의 root 값에 -1을 곱하고 right heap으로 트리 연산 삽입
 
    mid_value.append((left_heap[0])*(-1))   # left heap의 root 값을 중간 값으로 사용
 
for j in mid_value:
    print(j)