domw324   9달 전

머지소트 사용했구요.

시간복잡도 계산해보니까 O(N*logN)해서 연산은 3천만번 정도 밖에 안되는데

시간초과가 뜨네요.

왜 그런지 이해가 안가구요.. 어떻게 바꾸면 좋을지 알려주시면 감사하겠습니다~

koosaga   9달 전

nlgn이면 1억 천만번 아닌가요?

5백만개 원소 정렬하는 건 1.5초안에 빡빡한 경우가 많아서 다른 방법을 생각하시는게 좋을 거 같습니다. 

어림잡아 O(n) 정도에 되는 방법이 있어요. 

koosaga   9달 전

힌트 : selection algorithm을 찾아보시거나, std::nth_element 에 대해서 찾아보시길...

indioindio   9달 전

이 문제가 파이썬처럼 한 줄을 통째로 입력받으면 라이브러리의 정렬을 사용해도 시간 내에 간신히 들어올 수 있지만

그렇지 않다면 시간 내에 들어오기가 어렵습니다. (방금해보니 c언어로 빠른 입력 함수 + 퀵 소트로도 안되네요.)

퀵소트의 매 함수 호출마다 한 원소의 자리가 정해진다는 특성을 사용하셔야 할 것 같습니다.

domw324   9달 전

koosaga님, indioindio님 감사합니다.

제가 시간복잡도 계산을 잘못했네요 ㅠㅠㅠ...

한번 다시 풀어볼게요~ 감사합니다

baactree   9달 전

크 500백만 nlogn =  3천만 기적의 수학에 좋아요 누르고 갑니다.

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