akqjqcjs7   1년 전

문제는 해결 했지만 시간도 남들에 비해 오래걸렸고 코드도 개념을 이해하고

만들어 작성했지만 코드가 어색하다고 해야하나 그런 느낌이 듭니다.

이 코드에 불필요한 부분이나 개선이 필요한 부분을 알고 싶습니다.

pichulia   1년 전

400ms면 적당한 속도입니다. 100ms 미만인게 이상한겁니다.

굳이 따지자면 qsort 함수가 O(n log n)을 보장하지 않는다는 점이 신경쓰입니다.

akqjqcjs7   1년 전

제가 쓴 qsort가 신경쓰이신다는건가요?

그리고 제가 upper는 0부터n을 lower는 0부터 n-1을 이용했습니다. 구글링을 통해 배운거는

0부터 n까지 이용했습니다. 하지만 저는 lower는 n까지 할 필요가없다 생각했고 upper는 필요하다 판단해 n까지 했는데 맞는 판단일까요?

pichulia   1년 전

일반적인 lower_bound라면 arr[n-1] < data 인 경우 n을 return해야하기 때문에 0부터 n까지 보는게 좋긴 합니다만..  이 문제의 경우는 아무래도 상관없으니... 정답을 받았다면 상관없습니다.

그리고 qsort는 기본적으로 quick sort 알고리즘을 기반으로 동작하는데..  퀵소트는 그냥 n^2이라고 생각하시는게 속편합니다.

뭐 컴파일러가 이것저것 최적화를 했다곤 하지만 어찌됐든 공식적으로 O(n log n)을 보장하지 않는다고 했기 때문에 지양해야합니다.

akqjqcjs7   1년 전

친절한 답변 감사드립니다!

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