[힙] 백준 #1655 가운데를 말해요 - Python

🗂️ 문제

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

1655번: 가운데를 말해요

 

💡 접근법

중간값을 뽑아내기 위해서 최대 힙(leftHeap)과 최소 힙(rightHeap), 총 2개의 힙을 사용한다.

leftHeap에는 중간값보다 같거나 작은 값들이 저장되고, rightHeap에는 중간값보다 큰 값들이 저장된다.

 

leftHeap의 루트를 중간값으로 꺼낼 것이다. 이때 만약 수의 개수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말해야 한다는 문제 조건이 있다. 따라서 rightHeap과 leftHeap의 길이가 같을 경우에는 leftHeap에 새로운 값을 push해야 한다.

 

또한 만약 leftHeap의 루트가 rightHeap의 루트보다 클 경우에는 두 값을 swap해줘야 한다.

leftHeap의 루트는 중간값이다. 또한 leftHeap에는 중간값보다 작은 값들이 저장되어야 한다. 그런데 leftHeap의 루트가 rightHeap의 루트보다 크다면 중간값보다 작은 값이 rightHeap에 저장되어 있는 것이기 때문이다.

 

👀 배운 코드

import sys
import heapq

N = int(sys.stdin.readline())

leftHeap = [] # 최대 힙
rightHeap = [] # 최소 힙
for _ in range(N):
    x = int(sys.stdin.readline())
    
    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -x)
    else:
        heapq.heappush(rightHeap, x)

    if rightHeap and leftHeap and -leftHeap[0] > rightHeap[0]:
        large = heapq.heappop(leftHeap)
        small = heapq.heappop(rightHeap)
        
        heapq.heappush(leftHeap, -small)
        heapq.heappush(rightHeap, -large)
    
    print(-leftHeap[0])

 

🧐 배운 점

• 힙을 두 개를 생성하여 구현하는 방식을 잘 익혀두어야겠다.

 

✅ 정답 확인