글 읽기 - 시간초과 파이썬....

tkdlqm2 4년 전 0

로직을 확실히 짯고, 반복문도 한번 사용 했습니다.

왜 시간초과인지 모르겠습니다 ㅠ

N = int(input())
heap = []
anwser = []

for i in range(0,N):
    sentence = int(input())

    if sentence == 0: # 최대 힙 출력
        if len(heap) == 0:
            print(0)
        else:
            print(max(heap))
            heap.remove(max(heap))
    else:
        heap.append(sentence)

djm03178 4년 전 1

이름을 heap이라고 지었다고 해서 힙이 되는 게 아닙니다. 그냥 리스트입니다.

반복문을 한 번 썼다고 해서 시간이 빠른 것이 아니고 시간 복잡도를 계산해야 합니다. 리스트에서 최댓값을 찾는 건 리스트 전체를 순회해야 하므로 매번 O(N) 시간이 걸리고, 리스트에서 값을 지우는 것도 그 값을 찾는 데에 O(N), 지운 후 그 뒤의 원소들을 전부 한 칸씩 당겨오는 데에 O(N)이 걸립니다. 따라서 이 코드는 O(N^2)이니 시간 초과를 피할 수 없습니다.

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

문제

문제

출처

ICPC

시간초과 파이썬....

tkdlqm2 4년 전 0

djm03178 4년 전 1

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말