우선 질문게시판에 있는 반례들은 문제를 다 통과하는데, 그럼 정말 시간초과의 문제인걸까요...?
제가 문제를 푼 방법은 우선 수업들을 시작시간에 따라 정렬, 그 후 앞에서 수업 하나를 지우고 그 수업이 끝나고 시작하는 수업들 중 가장 빠른 수업을 지웁니다. 이런식으로 더 이상 지울 수업이 없을 때 강의실 하나 카운트. 이걸 수업들을 다 없에 버릴 때 까지 진행합니다.
질문을 드리고 싶은게 많은데 정리를 해보자면 아래와 같습니다.
1. 제 코드가 문제는 맞게 풀고 있을까요?
2. sort함수의 속도는 빠른 걸로 알고 있는데, 시간초과의 원인이 sort함수 때문은 아니겠죠? 제가 직접 합병정렬을 구현한다면 이것보다 더 빠를까요??
합병정렬을 구현해서 std::sort보다 더 빠르게 만들기는 어려울 겁니다. 그 부분보다는 만일 S=1,T=2만 200000개 들어오는 경우를 생각해보면 29번줄 while 반복 횟수 20만 회, 30번줄 for 반복 횟수 20만 회로 곱해서 시간제한 내에 해결할 수 없는 양이 됩니다.(+vector.erase() 함수도 O(N)의 시간복잡도를 먹습니다)
bearsff 2년 전 1
계속 4%즘에서 멈췄다가 시간초과가 뜹니다 ㅠㅠㅠ
우선 질문게시판에 있는 반례들은 문제를 다 통과하는데, 그럼 정말 시간초과의 문제인걸까요...?
제가 문제를 푼 방법은 우선 수업들을 시작시간에 따라 정렬, 그 후 앞에서 수업 하나를 지우고 그 수업이 끝나고 시작하는 수업들 중 가장 빠른 수업을 지웁니다. 이런식으로 더 이상 지울 수업이 없을 때 강의실 하나 카운트. 이걸 수업들을 다 없에 버릴 때 까지 진행합니다.
질문을 드리고 싶은게 많은데 정리를 해보자면 아래와 같습니다.
1. 제 코드가 문제는 맞게 풀고 있을까요?
2. sort함수의 속도는 빠른 걸로 알고 있는데, 시간초과의 원인이 sort함수 때문은 아니겠죠? 제가 직접 합병정렬을 구현한다면 이것보다 더 빠를까요??
3. 도대체 시간초과를 어떻게 해결 할 수 있을까요??
도움 부탁드립니다... 감사합니다!