[백준/파이썬] 1655번

📍백준 1655번 문제

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

코드

import heapq
import sys

input = sys.stdin.readline

n = int(input())
ans = []
leftHeap = []  # 중간값보다 작은 수 , 최대힙
rightHeap = []  # 중간값보다 큰 수 , 최소힙
for i in range(n):
    num = int(input())
    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, (-num, num))
    else:
        heapq.heappush(rightHeap, (num, num))
    if rightHeap and leftHeap[0][1] > rightHeap[0][0]:
        min = heapq.heappop(rightHeap)[0]
        max = heapq.heappop(leftHeap)[1]
        heapq.heappush(leftHeap, (-min, min))
        heapq.heappush(rightHeap, (max, max))
    ans.append(leftHeap[0][1])

for j in ans:
    print(j)

풀이

• leftHeap에는 중간값보다 작은수가, rightHeap에는 중간값보다 큰수가 들어간다.
  중간값의 경우, 외친 개수가 짝수개라면 2개의 값중 작은 값을 출력해야 하므로 leftHeap있어야 한다.
• leftHeap은 최대힙, rightHeap은 최소힙으로 구현하여 leftHeap의 루트값이 중간값으로 만들어준다.
• 만약, 두 힙의 길이가 같다면, 중간 값이 들어있는 leftHeap에 값을 넣는다. 아니라면, rightHeap에 값을 넣어준다.
• 만약 leftHeap의 루트 값(leftHeap에서 가장 큰 값)이 rightHeap의 루트 값(rightHeap에서 가장 작은 값)보다 크다면 서로 값의 위치를 바꿔준다.(중간 값이 rightHeap의 루트 값이므로)