개발자 톡
연습문제 톡
강의실 배정
강의실 배정 python 시간 초과 질문입니다
- 등록일
- 2022-04-22 00:20:30
- 조회수
- 941
- 작성자
- hyunn131
Python으로 아래와 같이 코드를 작성하였는데, 시간 초과가 발생합니다.
최대 시간이 걸린 케이스 기준으로
입력값(input)을 받아오는데 600ms 정도가 걸렸고,
내장함수 list.sort()를 이용한 정렬을 마치면 총 2090ms 가량이 소요되어 시간 초과가 발생합니다.
알골선생 풀이(링크: Softeer) 역시 같은 로직으로, 종료 시간을 기준으로 정렬 후 강의실을 배정하여 O(nlogn)의 시간복잡도를 가지는데 시간 초과가 왜 발생하는지 모르겠습니다.
1) 내장함수인 list.sort()에서 사용되는 Tim sort는 일반적인 경우에 빠르며 배열이 완전 무작위인 최악의 경우에도 시간복잡도가 O(nlogn)인 것으로 알고 있고 있는데, Python으로 이 문제를 해결할 수 있는 다른 정렬 방법이나 알고리즘이 있는 것인지 궁금합니다.
2) 최대 입력값을 고려해보면 필요 연산이 C*106 *log106 정도로 대략 C *20,000,000(C*2000만) 정도로 예상되는데, pypy를 이용하면 충분히 2초 이내에 연산이 가능할 것으로 보이는데 시간 초과가 나는 이유도 궁금합니다.
import sys
N =
int(sys.stdin.readline().rstrip())
table = [
tuple(
map(
int, sys.stdin.readline().rstrip().split()))
for _
in
range(N)]
table.sort(key =
lambda x: x[
1])
e =
0
cnt =
0
for i,j
in table:
if e <= i:
cnt +=
1
e = j
print(cnt)
#강의실_배정
#python