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

문제 보기

[사용한 알고리즘]

우선순위 큐(Priority Queue)

 

[문제 접근]

두 개의 heap을 이용하여 중간값을 관리하였습니다. 왼쪽 힙을 left(max heap), 오른쪽 힙을 right(min heap)라고 가정하면 left와 right의 보유 원소 개수(길이)가 같으면 left에 무조건 삽입합니다. 이외에는 right에 삽입합니다. 그리고 만약 left의 가장 큰 값과 right의 가장 작은 값을 비교해서 left의 가장 큰 값이 더 크면 left의 가장 큰 값과 right의 가장 작은 값을 바꿔줍니다. 그러면 right의 가장 큰 값은 중간값이기 때문에 효율적으로 중간값을 관리할 수 있습니다.

 

[알고리즘]

1. 두 개의 heap을 선언합니다. left(max heap), right(min heap)

 -> Python의 heap은 최소 힙이기 때문에 max heap으로 사용하려면 삽입하려는 수에 -를 붙이면 됩니다.

2. 두 개의 heap 크기가 같으면 left에 삽입합니다.

3. 두 개의 heap 크기가 다르면 right에 삽입합니다.

4. left max 값과 right min 값을 비교한 후 left max 값이 더 크면 right min값과 교체합니다.

5. left의 max값을 출력합니다.

 

[코드]

import sys
import heapq


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    max_h, min_h = [], []

    # max_h[0][1]값을 기준으로 큰 값은 min_h, 같거나 작은 값은 max_h에 삽입
    for _ in range(n):
        num = int(sys.stdin.readline())
        if len(max_h) == len(min_h):
            heapq.heappush(max_h, (-num, num))
        else:
            heapq.heappush(min_h, (num, num))
        if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0][1] > min_h[0][1]:
            max_value = heapq.heappop(max_h)[1]
            min_value = heapq.heappop(min_h)[1]
            heapq.heappush(max_h, (-min_value, min_value))
            heapq.heappush(min_h, (max_value, max_value))
        print(max_h[0][1])