cereme   2년 전

스택을 사용하여 구현하였습니다.

(d, t)튜플 리스트인 dtlist를 t 내림차순으로 정렬하고 가장 큰 t로 nowday를 초기화였습니다.

그리고 1씩 내려가면서 스택을 채워나가다가 과제를 모두 완료 (counter  +1 == len(dtlist) )하였을때 루프를 종료하고 답을 계산하는 방식으로 짰는데 시간 초과가 뜨네요...

이거 O(N) 아닌가요?? 어디가 문제인지...

chogahui05   2년 전

처음에 nowday는, 제출 기한 중 가장 큰 day로 초기화가 되었네요.

예를 들어서, 아래 4개의 data가 들어왔다고 가정하면

60,000,000 100,000,000

2,000,000 10,000,000

2 8

3 7

day = 100,000,000로 초기화가 되겠군요.

foo는 잘 모르겠지만, for ~ in range ~ 문에 의해서

60,000,000번 돌겠군요.


2번째를 읽어봅시다. 현재 now_day가 40,000,000이네요.

그리고, dtlist[~][1]이 10,000,000인데요.

이 경우, 1000만이 4000만보다 작으므로 else문으로 가겠네요. 언제까지? now_day가 10,000,000보다 작아질 때 까지요.


굳이 day를 1씩 감소시킬 필요가 있을까요?


어떤 식으로 돌아가시는 지 요약해서 알려드렸습니다만.

시간 복잡도는 O(제출 기한이 가장 높은 day)가 되겠는데요. 제출기한이 가장 높은 day는 10억이므로..

시간초과가 나겠네요. 다른 방법을 써 보세요.

cereme   2년 전

감사합니다. 덕분에 문제상황 인식했습니다!

댓글을 작성하려면 로그인해야 합니다.