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

문제

구조

왼쪽 힙은 최대 힙으로 정렬하고, 오른쪽 힙은 최소 힙으로 정렬하면
왼쪽 힙의 첫번째 요소는 항상 중앙값이 된다.

이때 왼쪽 힙의 첫번째 요소는 최대 힙에서 가장 큰 값이다.
마찬가지로 오른쪽 힙의 첫번째 요소는 최소 힙에서 가장 작은 값!

1-1. leftheap과 rightheap의 길이가 같으면 해당 숫자를 leftheap에 넣음
1-2. 길이가 같지 않다면 길이를 맞춰주기 위해 rightheap에 넣음 (번갈아가면서 넣는다고 생각)
2-1. leftheap의 루트가 rightheap의 루트보다 크면 leftheap의 루트와 rightheap의 루트를 바꿔준다.
=> 이유: leftheap은 중간값을 기준으로 작은 수가 들어가는 곳
leftheap의 루트가 rightheap의 루트보다 크면(두 힙 모두 안에 원소가 있어야 함) 중간값보다 큰 수가 leftheap에 들어가게 되므로 leftheap의 루트와 rightheap의 루트를 바꿔줌
2-2. 두 루트를 바꿔주려면 먼저 두 개의 힙에서 최솟값을 pop해줘야 함!
그 다음에 pop 해준 루트 값들을 heappush() 메소드를 써서 넣어준다.
3. 다 넣어주고 나면 leftheap의 루트가 중간값이 됨!

https://velog.io/@uoayop/BOJ-1655-가운데를-말해요Python

heapq 모듈

import heapq

h = []  # 힙 생성
for score in data:
    heapq.heappush(h, score)  # 힙에 데이터 저장

for i in range(3):
    print(heapq.heappop(h))  # 최솟값부터 힙 반환 (루트)

풀이

참고 블로그
https://velog.io/@uoayop/BOJ-1655-가운데를-말해요Python
https://hongcoding.tistory.com/93

import sys
import heapq

N = int(sys.stdin.readline())
leftheap = []
rightheap = []

for i in range(N):
    n = int(sys.stdin.readline())

    if len(leftheap) == len(rightheap):
        heapq.heappush(leftheap, (-n, n))
    else:
        heapq.heappush(rightheap, (n, n))
    
    if len(leftheap) > 0 and len(rightheap) > 0 and leftheap[0][1] > rightheap[0][1]:
        # leftheap의 루트와 rightheap의 루트를 바꿔주기 위해서는 push를 해주기 전에
        # 미리 pop을 해줘야 함 (그래야 바꿀 수 있음!)
        
        # 최솟값부터 힙 반환 (우선순위 순서대로 값을 꺼내올 수 있음!)
        leftnum = heapq.heappop(leftheap)
        rightnum = heapq.heappop(rightheap)
        heapq.heappush(leftheap, (-rightnum[1], rightnum[1]))
        heapq.heappush(rightheap, (leftnum[1], leftnum[1]))

    print(leftheap[0][1])