백준 1655 - 가운데를 말해요 (파이썬)

Answer

import sys

def insert_right(heap, num):
    heap.append(num)
    i = len(heap) - 1

    while i > 1:
        if heap[i] < heap[i // 2]:
            heap[i], heap[i // 2] = heap[i // 2], heap[i]
            i //= 2
        else:
            break

def remove_right(heap):
    min_val = heap[1]
    tmp = heap.pop()

    parent = 1
    child = 2
    heap_len = len(heap)

    while child <= heap_len - 1:
        if child < heap_len - 1 and heap[child] > heap[child + 1]:
            child += 1

        if heap[child] >= tmp:
            break

        heap[parent] = heap[child]

        parent = child
        child *= 2

    if heap_len != 1:
        heap[parent] = tmp

    return min_val

def insert_left(heap, num):
    heap.append(num)
    i = len(heap) - 1

    while i > 1:
        if heap[i] > heap[i // 2]:
            heap[i], heap[i // 2] = heap[i // 2], heap[i]
            i //= 2
        else:
            break

def remove_left(heap):
    max_val = heap[1]
    tmp = heap.pop()

    parent = 1
    child = 2
    heap_len = len(heap)

    while child <= heap_len - 1:
        if child < heap_len - 1 and heap[child] < heap[child + 1]:
            child += 1

        if heap[child] <= tmp:
            break

        heap[parent] = heap[child]

        parent = child
        child *= 2

    if heap_len != 1:
        heap[parent] = tmp

    return max_val

n = int(sys.stdin.readline())
left_heap = [0]
right_heap = [0]

for _ in range(n):
    num = int(sys.stdin.readline())

    if len(left_heap) == len(right_heap):
        insert_left(left_heap, num)
    else:
        insert_right(right_heap, num)

    if len(right_heap) > 1 and left_heap[1] > right_heap[1]:
        max_val = remove_left(left_heap)
        min_val = remove_right(right_heap)
        insert_left(left_heap, min_val)
        insert_right(right_heap, max_val)

    print(left_heap[1])