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

관심 Tag

Talk 등록

Dev. Talk

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

회원사진hyunn131
653 views2022-04-22 00:20

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)