퀵소트가 느리기 때문입니다. 버블 정렬과 같은 O(n^2)이므로 더 빠른 O(nlogn)의 정렬을 써야 합니다.
2751번 - 수 정렬하기 2
퀵소트의 pivot을 위와 같이 start로만 잡게 되면, 초기 배열이 오름차순이거나 내림차순인 경우 5,4,3,2,1 -> 4,3,2,1 -> 3,2,1 -> 2,1 -> 1과 같이 정렬을 하기 때문에 O(n^2)입니다.
pivot을 start,end의 중간값으로 잡거나 랜덤한 위치로 설정하면 간단하게 해결할 수 있지만 무조건 O(nlogn)을 보장하지는 않습니다.
더 자세한 내용은 구글에 퀵소트 pivot으로 검색하시면 될 것 같습니다!
http://boj.kr/8ea24d77b0c848ba...
http://boj.kr/2a03cb2f59544b8c...
이 문제에서는 중간값으로 잡으면 시간초과가 걸려서 무조건 랜덤피봇으로 설정해야 하는것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
lggp 2년 전
퀵소트를 사용했는데도 시간초과를 당했는데 이유를 알 수 있을까요?