아직 계정이 없으신가요? 회원가입

Dev. Talk

강의실 배정 python 시간 초과 질문입니다2

회원사진hyunn131
184 views2022-04-22 15:11

이전 질문 링크: Softeer


최소힙을 사용하여 문제를 해결하였습니다. 그런데


1) 한번에 heapify (O(n))진행 후, 하나 씩 heappop(O(nlogn))을 하는 경우(전체 O(nlogn))에는 시간초과가 발생하고

2) 하나 씩 heappush (O(nlogn))진행 후, 하나 씩 heappop(O(nlogn))을 하는 경우(전체 O(nlogn))에는 통과합니다.


일반적으로 힙정렬이 다른 정렬에 비해 일반적으로 느린 편으로 알고 있고, 1)의 경우에도 Tim sort를 진행한 경우보다 느린 것을 확인 할 수 있었습니다. 

2)의 경우가 1)과 Tim sort보다 빠르게 진행되는 이유가 궁금합니다. (n의 크기가 충분히 크지 않아 상수 C의 차이가 더 중요한 것일지도 모릅니다. (실제 동작시간: Cnlogn+a))


추가적으로 1),2), list.sort()(Timsort) 세 가지 풀이 모두 시간 복잡도는 O(nlogn)으로 동일합니다. 문제의 의도가 같은 로직이라도 시간복잡도의 풀이 중에서도 적은 시간을 파악하여 푸는 것인지, Python의 경우 한번에 정답을 맞추는 것이 가능한 지 궁금합니다.



1) 코드

import sys
from heapq  import heapify, heappop
N =  int(sys.stdin.readline().rstrip())
table = [ tuple( map( int, sys.stdin.readline().rstrip().split()))  for _  in  range(N)]
heapify(table)

e =  0
cnt =  0
while table:
    i,j = heappop(table)
     if e <= i:
        cnt +=  1
        e = j
print(cnt)

2) 코드

import sys

from heapq  import heappush, heappop
N =  int(sys.stdin.readline().rstrip())
table = []
for _  in  range(N):
    i,j =  list( map( int, sys.stdin.readline().rstrip().split()))
    heappush(table, (j,i))

e =  0
cnt =  0
while table:
    j,i = heappop(table)
     if e <= i:
        cnt +=  1
        e = j
print(cnt)