whazzulookinat   5년 전

C를 이용해 BST 구현을 하였고, 특히 insert 과정에서 입력이 worst case로 되는 경우(1,2,3,4,5,6)를 방지하기 위해 정렬 후 중간부터 옆으로 하나씩 이동하면서 넣어주며 balancing property를 유지해주었습니다. 그런데도 계속 시간초과가 뜨네요.. 혹시 어떤 부분이 시간초과를 초래했을까요..

djm03178   5년 전

이 문제는 시간복잡도에 로그를 붙여서는 통과하기 어렵습니다. 해싱으로 평균 O(1)에 풀기를 의도한 문제입니다. 그래도 시간이 매우 빠듯합니다.

greedev   5년 전

머지소트 + 이분 탐색으로 풀립니다

djm03178   5년 전

채점 서버가 많이 빨라지긴 했군요. 로그를 쓴다면 아마 상수를 많이 최적화해야 될 거고, fast I/O도 도움이 많이 될 것 같습니다.

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