글 읽기 - 시간초과 질문 드립니다.

hsw0194 2년 전 0

running median 문제여서 아래처럼 구현 했는데 시간초과가 나네요 어느부분이 문제일까요?

from sys import stdin
import heapq as hq

N = int(stdin.readline())


def add_number(number, max_heap, min_heap):

    if len(max_heap) == 0 or number < max_heap[0][1]:
        hq.heappush(max_heap, (-number, number))
    else:
        hq.heappush(min_heap, (number, number))


def rebalance(max_heap, min_heap):
    bigger = max_heap if len(max_heap) > len(min_heap) else min_heap
    smaller = min_heap if len(max_heap) > len(min_heap) else max_heap

    if len(bigger) - len(smaller) >= 2:
        # value=hq.heappop(bigger)[1]
        value = bigger[0][1]
        del bigger[0]

        if smaller == max_heap:
            hq.heappush(smaller, (-value, value))
        else:
            hq.heappush(smaller, (value, value))


def get_median(max_heap, min_heap):
    bigger = max_heap if len(max_heap) > len(min_heap) else min_heap
    smaller = min_heap if len(max_heap) > len(min_heap) else max_heap

    # 개수가 같으면 작은것이 중간값
    if len(bigger) == len(smaller):
        return smaller[0][1]
    else:
        return bigger[0][1]


def sol():
    # max_heap : max heap
    # min_heap : min heap
    max_heap, min_heap = list(), list()
    for _ in range(N):
        num = int(stdin.readline())
        add_number(num, max_heap, min_heap)
        rebalance(max_heap, min_heap)
        print(get_median(max_heap, min_heap))


sol()

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문 드립니다.

hsw0194 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말