yshyjn   7년 전

시간초과가 나오는데 어디가 잘못된건지 잘 모르겠어요,,

yclock   7년 전

34번째 줄의 while문이 O(N2)으로 보여집니다.

O(N log N) 알고리즘으로 풀어주세요.

1207koo   7년 전

위의 분이 틀린 것 같습니다

34번째 줄은 O(N)이고요 (k가 있기 때문에)

문제는 거기서 무한루프를 돕니다.

35번째 줄의 for문에서 만약 만족하는 i가 없는 경우에도 break되도록 해주세요


자세히 설명하자면 k를 여러 번 설정하다가 i=n-1인데도 만족하는 i가 없으면 다시 같은 상태에서 while문을 시작합니다.

yclock   7년 전

@1207koo

그렇군요. 34번째 줄은 O(N)이 맞습니다.

35번째 줄의 for문의 예외처리가 필요합니다.


22번째 줄의 정렬도 신기하네요;;

만약 저 알고리즘이 정상적으로 작동한다면, "정렬 하한은 O(N)이다"라고 논문 쓰셔야 할 듯 합니다.

1207koo   7년 전

정말 22번째 줄 정렬도 이상합니다...;;

O(N)이네요...

또한 이 문제에서는 끝나는 시간만이 아니라 시작하는 시간으로도 정렬되야합니다.(이것은 끝나는 시간이 같을 경우)


아무튼 정렬부분은 버블소트로 하려고 하신 듯 한데.....안됩니다....O(N^2)입니다...

sort함수 쓰세요.차라리....(아니면 정렬 O(NlogN)으로 짤 수 있으면 직접 짜면 되는데 어차피 함수 있으니 그걸 쓰는 것이 낫겠죠...)

sort함수는 정답 코드 몇 개 보면 있을 겁니다.

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