BOJ 1655 가운데를 말해요

문제 : BOJ 1655 가운데를 말해요

입력이 주어질 때 마다 현재까지 입력된 값 중 중간값을 출력해야 한다.
입력된 값의 개수가 짝수라면, 두 중간값 중 작은값을 출력한다.

우선순위 큐를 이용해서 문제를 해결하였다.

어떻게

최소힙과 최대힙을 이용해서
둘 중 하나의 root가 항상 현재까지의 입력의 중간값이 되도록 유지시켜주어야 한다.

어떻게

두 힙의 root에 위치하는 값의 크기와 각 힙의 길이를 이용한 조건으로
각각의 입력을 어떤 힙에 넣어야 하는지 판단해주었다.

어떻게 1 (입력)

입력 받은 수를 각 힙(최소, 최대)의 front에 있는 값과 비교하여
각 힙의 front가 중간 값을 유지하도록 저장해 주었다.

첫번째 입력(최대, 최소 힙 모두 비어있을 경우) 또는
최대힙의 front보다 입력값이 작을 경우에만 최대힙에 넣어주고,
그 외의 경우에는 최소힙에 넣어준다.

어떻게 2 (유지)

각 힙의 길이를 비교한다.
길이가 2 차이가 나면, 두 힙의 front가 중간값의 후보가 될 수 없다.
따라서 길이가 긴 쪽에서pop(), 짧은 쪽에서 그 값을 push() 해준다.

어떻게 3 (판단)

두 힙의 front 중 누가 중간값인지 아직은 모른다.
길이가 다르면, 긴쪽의 front가 중간값이다.
길이가 같으면, 문제의 조건에 따라 둘 중 작은 값을 꺼내야한다.

[ 전체 코드 ]

import sys
# heapq 는 기본적으로 Min Heap 임
import heapq

n = int(sys.stdin.readline().rstrip())

max_heap = []
min_heap = []

while n > 0:
    k = int(sys.stdin.readline().rstrip())


    # [ 값 저장 ]

    # 1. 길이가 0 이거나(첫 입력), 
    # 2. max_heap의 root보다 k가 작을 경우에만
    # max_heap에 push
    if len(max_heap) == 0 or -max_heap[0] > k:
        # max_heap으로 사용하기 위해서 부호를 반대로 바꿔줌
        heapq.heappush(max_heap, -k)
    # 그 외의 경우는, min_heap에 push
    else:
        heapq.heappush(min_heap, k)


    # [ 중간값 유지를 위한 힙 간 값 전달 ]

    # 양 heap의 길이가 2 이상 차이나면 
    # 긴 쪽에서 pop()한 값을 짧은 쪽에서 push() 받음
    if len(max_heap) > len(min_heap)+1:
        heapq.heappush(min_heap, -heapq.heappop(max_heap))
    elif len(min_heap) > len(max_heap)+1:
        heapq.heappush(max_heap, -heapq.heappop(min_heap))


    # [ 현재 중간값이 있는 힙을 판별 ]

    # 두 힙의 길이가 같다면
    if len(min_heap) == len(max_heap):
        # 중간값은 두 힙의 root값 중 작은 값인 max heap의 root
        mid = -max_heap[0]
        sys.stdout.write(f'{mid}\n')
    # 두 힙의 길이가 다르다면
    else:
        # 중간값은 두 힙 중 길이가 긴 힙의 root값
        mid = min_heap[0] if len(min_heap) > len(max_heap) else -max_heap[0]
        sys.stdout.write(f'{mid}\n')

    n -= 1