글 읽기 - 도와주세요 ㅠㅠ(파이썬)

qwerty1434 2년 전 0

직접 힙정렬을 구현해보고 있는데 계속 시간초과가 발생합니다

어느 부분을 어떻게 고쳐야 하는지, 무엇이 문제인지 좀 알려주시면 감사하겠습니다

def heapify(lst,n):
    for i in range(1,n):
        c = i
        while c != 0: 
            root = (c-1)//2
            if lst[root] < lst[c]:
                lst[root],lst[c] = lst[c],lst[root]
            c = root
        
import sys
lst = []
for i in range(int(sys.stdin.readline())):
    x = int(sys.stdin.readline())
    if x == 0:
        if not lst:
            print(0)
        else:            
            n = len(lst)
            heapify(lst,n)
            lst[0],lst[n-1] = lst[n-1],lst[0]
            print(lst.pop())
            
    else:
        lst.append(x)  
        

wider93 2년 전 0

이 heapify 함수는 시간복잡도 O(nlogn)을 가지고 있습니다. 이 함수는 기존 리스트가 힙 구조와 전혀 관련이 없이 정렬되어있는 첫 상황에 사용할 만한 것으로, 이미 힙인 리스트에 원소 하나를 더할 때 사용할만한 함수가 아닙니다.

qwerty1434 2년 전 0

그렇군요 덕분에 어느 부분이 틀린건지 알게 되었습니다
다시한번 작성해봐야 겠군요 감사합니다 :)

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

문제

문제

출처

ICPC

도와주세요 ㅠㅠ(파이썬)

qwerty1434 2년 전 0

wider93 2년 전 0

qwerty1434 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말