Softeer

Home
Connect

관심 Tag

Talk 등록

Dev. Talk

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

hyunn131

457 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))