가운데를 말해요

문제

[백준 1655번 문제] 가운데를 말해요

풀이

1. 최대 힙과 최소 힙 초기화: 최대 힙은 항상 최소 힙보다 같거나 하나 더 많은 요소를 가지도록 유지합니다.
2. 새로운 수 추가: 새로운 수를 받을 때마다 다음의 두 조건 중 하나를 따릅니다:
   • 최대 힙과 최소 힙의 길이가 같다면 최대 힙에 새 수를 추가합니다.
   • 그렇지 않다면 최소 힙에 추가합니다.
3. 힙 조정: 만약 최소 힙의 최소 요소가 최대 힙의 최대 요소보다 작다면 두 요소를 교환합니다. 이는 두 힙이 각각 중간값 이하와 이상의 값들을 유지하도록 보장합니다.
4. 중간값 출력: 각 단계에서 최대 힙의 최대값(루트)가 현재까지의 중간값이 됩니다.

파이썬 코드

import heapq
import sys


if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    max_heap, min_heap = [], []
    results = []

    for _ in range(N):
        num = int(input())

        if len(max_heap) == len(min_heap):
            # heapq 모듈은 기본적으로 최소 힙만 있기 때문에 인위적으로 최대 힙을 만듦
            heapq.heappush(max_heap, (-num, num))
        else:
            heapq.heappush(min_heap, (num, num))

        if min_heap and max_heap[0][1] > min_heap[0][0]:
            max_val = heapq.heappop(max_heap)[1]
            min_val = heapq.heappop(min_heap)[0]
            heapq.heappush(max_heap, (-min_val, min_val))
            heapq.heappush(min_heap, (max_val, max_val))

        results.append(max_heap[0][1])

    for result in results:
        print(result)

팁

heapq는 Python에서 힙 구조를 제공하는 모듈입니다. 힙은 모든 부모 노드가 자식 노드보다 크거나 같은(최대 힙) 또는 작거나 같은(최소 힙) 이진 트리입니다. heapq 모듈은 기본적으로 최소 힙을 제공합니다.

• heapq.heappush(heap, item): item을 heap에 추가합니다.
• heapq.heappop(heap): heap에서 가장 작은 요소를 pop하고 반환합니다.
• 최대 힙을 구현하려면, 값을 튜플로 넣을 때 (-값, 원래값)과 같이 넣어서 우선순위를 반대로 설정합니다.

이 문제에서는 최대 힙과 최소 힙을 사용하여 중간값을 효율적으로 관리합니다. 최대 힙은 중간값보다 작은 값들을, 최소 힙은 중간값보다 큰 값들을 저장하면서, 항상 최대 힙의 루트가 중간값이 되도록 유지합니다.