개발자 톡
연습문제 톡
강의실 배정
강의실 배정 python 시간 초과 질문입니다2
- 등록일
- 2022-04-22 15:11:58
- 조회수
- 931
- 작성자
- hyunn131
이전 질문 링크: 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)
#강의실_배정
#python