parkkpu   4달 전

두가지 방법으로 해봤는데 문제가 무엇인지 모르겠습니다.

하나는 런타임에러 하나는 시간초과라고 뜨네요.

문제가 무엇인지 모르겠습니다.

도와주세요ㅜㅜ

highalps   4달 전

N이 상당히 크기 때문에, 일반적인 sort 함수로는 답을 구해내기 힘듭니다.

제가 알기론, C++에서의 sort 함수는 대략적으로 퀵소트로 돌아가는 것으로 알고 있는데, 퀵소트는 worst case인 경우 시간 복잡도가 O(n^2) 입니다.


따라서 무조건 O(nlogn)의 시간 복잡도를 가지는 merge sort를 직접 구현 해보시거나 (이것도 맞을지는 확실히 모르겠습니다)
아니면 Quick selection 에 대해서 찾아보시는 게 좋을 것 같습니다.

혹은 nth_element 라는 k번째 위치한 element를 찾는 함수가 있는데, 역시 Quick selection에 대해서 선행하시고 난 뒤 사용하는 것을 추천합니다

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