글 읽기 - 이건 왜 시간초과가 날까요

chminoo 4년 전 1

힙이라는 걸 알게된지 조금밖에 안되서 최대한 응용해가면서 하고 있는데요

이건 왜 시간초과가 뜰까요?

heappop을 사용하면 가장 위루트에서 값을 쏙 빼고 하나씩 작은순대로 호로록 올라오니까 pop시킨걸 temp에 넣어놓고 프린트 한뒤에 다시 큐에다가 뺀걸 extend시킨다음 heapify시켜서 힙정렬 해줬습니다

요것들 하나하나가 잡아먹는 복잡도를 잘 몰라서 우선 해봤는데 시간초과가 뜨네용..

import sys
import heapq


n = int(sys.stdin.readline())
queue = []
for _ in range(n):
    tmp = int(sys.stdin.readline())
    temp = []
    heapq.heappush(queue, tmp)
    for i in range(_//2):
        temp.append(heapq.heappop(queue))
    print(queue[0])
    queue.extend(temp)
    heapq.heapify(queue)

sait2000 4년 전 2

전체 O(n^2 log n)입니다. 12번 줄이 O(n^2)번 실행되니까요. heappop, heappush는 heap의 크기를 n이라 하면 O(log n)이고 heapify는 O(n)입니다.

dyk777 4년 전 2

힙정렬 없이, 힙의 push와 pop만으로 구현해야 할 겁니다.

힙정렬은 자체 시간복잡도가 O(nlgn)인데, 이를 n개의 원소가 삽입/삭제될때마다 하면 최악 O((n^2)lgn)이 되겠네요.

chminoo 4년 전 0

아 그렇군요 다들 감사합니다

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

문제

문제

출처

ICPC

이건 왜 시간초과가 날까요

chminoo 4년 전 1

sait2000 4년 전 2

dyk777 4년 전 2

chminoo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말