이 문제의 본래 의도는 단순히 정렬을 해서 K번째 수를 빼오는 것이 아닌 것으로 추정됩니다. N이 지나치게 커 보이는 건 이 때문입니다. 이 문제의 의도대로 문제를 풀고 싶으시다면 quickselect(quicksort가 아니라)라는 알고리즘을 공부해야 합니다. 정렬을 해서 O(NlogN)에 해결하는 것이 아닌, O(N)에 문제를 해결할 수 있게 됩니다.
하지만 안타깝게도 이 문제에는 허점이 많습니다. O(NlogN)의 정렬보다도 일반적으로 훨씬 더 큰 비중을 차지하는 것은 바로 입력 시간입니다. 입력 시간만 단축해도 정렬로 손쉽게 해결이 가능합니다. 단순히 정렬로 문제를 해결하고 싶으시다면, https://www.acmicpc.net/proble... 를 보고 언어별로 입력 시간을 단축하는 법을 알아보세요.
오히려 quickselect의 경우 잘 구현하지 않으면 quicksort와 마찬가지로 피벗이 한쪽으로 쏠리는 문제가 발생하여 최악의 경우 O(N^2)이 됩니다. 물론 quicksort로 정렬을 할 때에도 마찬가지입니다.
https://www.acmicpc.net/board/view/31887 를 참고하세요.
이론적으로 quickselect는 worst case O(N)이 가능하지만, 항상 O(N)을 보장하기 위한 평균 케이스의 오버헤드가 너무 크기 때문에 C++에서는 최악의 경우 O(NlogN) 이상만 보장해줄 것을 명시하고 있습니다. 이를 구현한 함수가 nth_element입니다.
djm03178 4년 전 12