bearsff   2년 전

계속 4%즘에서 멈췄다가 시간초과가 뜹니다 ㅠㅠㅠ

우선 질문게시판에 있는 반례들은 문제를 다 통과하는데, 그럼 정말 시간초과의 문제인걸까요...?

제가 문제를 푼 방법은 우선 수업들을 시작시간에 따라 정렬, 그 후 앞에서 수업 하나를 지우고 그 수업이 끝나고 시작하는 수업들 중 가장 빠른 수업을 지웁니다. 이런식으로 더 이상 지울 수업이 없을 때 강의실 하나 카운트. 이걸 수업들을 다 없에 버릴 때 까지 진행합니다.

질문을 드리고 싶은게 많은데 정리를 해보자면 아래와 같습니다.

1. 제 코드가 문제는 맞게 풀고 있을까요?

2. sort함수의 속도는 빠른 걸로 알고 있는데, 시간초과의 원인이 sort함수 때문은 아니겠죠? 제가 직접 합병정렬을 구현한다면 이것보다 더 빠를까요??

3. 도대체 시간초과를 어떻게 해결 할 수 있을까요??

도움 부탁드립니다... 감사합니다!

yijw0930   2년 전

합병정렬을 구현해서 std::sort보다 더 빠르게 만들기는 어려울 겁니다. 그 부분보다는 만일 S=1,T=2만 200000개 들어오는 경우를 생각해보면 29번줄 while 반복 횟수 20만 회, 30번줄 for 반복 횟수 20만 회로 곱해서 시간제한 내에 해결할 수 없는 양이 됩니다.(+vector.erase() 함수도 O(N)의 시간복잡도를 먹습니다)

arr 벡터를 한 번만 보면서 해결할 방법이 존재할 것이라고 생각합니다.

bearsff   2년 전

질물에 대한 답변 감사합니다! 덕분에 궁금증들이 다 해결되었습니다 :)

정말S=1,T=2만 200000개와 같이 들어오는 경우에는 계산값이 많아지겠군요. 말씀해주신대로 arr 벡터를 한 번만 보는 방법으로 풀어서 맞출 수 있었습니다!

다시 한 번 감사합니다!

hacastle   2년 전

감사합니다~

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