BOJ 11004 K번째 수

n이 5000000(오백만)이라 O(nlogn) sort를 써도 될 것 같지만 시간초과가 난다고 하는데, 아마 입력받는데도 시간이 꽤 걸려서 인 것 같다.

그런데 O(n)만에 k번째 수를 찾는 방법이 있다고 한다!
바로 Quick Selection이라는 것인데, Quick Sort와 똑같다고 보면된다. Quick Sort를 조금 변형한 것이다.

오름차순 기준으로 간단히 설명하자면 Quick Sort는 pivot을 기준으로 pivot보다 작은 수를 왼쪽에, 큰 수를 오른 쪽으로 배치함으로써 pivot의 위치를 찾고, 확정된 그 pivot의 위치를 기준으로 나눠 또 그 안에서 pivot의 위치를 찾는 분할 정복 방식인데, k번째 수를 찾을 때는 pivot을 기준으로 양쪽을 다 볼 필요가 없다. 만약 pivot이 우리가 찾고자 하는 k번째 수라면 바로 pivot을 return하면 되지만, 아니라면 pivot의 왼쪽이나 오른쪽 중 한 곳만 계속해서 탐색하면 되는 것이다.

그래서 N+N/2+N/4+....이렇게 해서 O(2N) => O(N)이 나오는 것이다. 물론 최악의 경우에는 N제곱이 나올 것 같기도 하다... 하지만 pivot을 잘 고르고, N이 크면 클 수록 최악의 경우는 거의 나오지 않는 것으로 알려져있다.

참고
윤성우의 열혈 자료구조(ORANGE MEDIA)

참고 링크
http://programbasic.tistory.com/403

http://createcode.tistory.com/entry/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Quick-Sort-%ED%80%B5%EC%86%8C%ED%8A%B8

http://hackability.kr/entry/Quick-Selection%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-On-%EC%84%A0%ED%83%9D-%EB%B0%A9%EB%B2%95


주의 사항

pivot을 가장 왼쪽, 가운데, 가장 오른쪽 값중 중간 값으로 정해주는 방식으로 구현해보려고  했는데, 내가 사용한 코드는 pivot을 가장 왼쪽 값으로 놨을 때 기준이기 때문에 문제가 계속 발생했다. 아무 값이나 pivot으로 잡아서 하기 때문에 중간에 pivot이 어떤 값과 swap이 일어날 수도 있었고, 무한 루프에 빠지기도 했다. 그래서 내가 직접 아무값이나 pivot으로 놓는 코드를 구현해보려 했는데, 그러면서 알게 된 것이 있다. pivot의 위치를 한 곳으로 고정시켜놓는 것이 편하단 것이다... 직접 해보니까 알게 되었다.
"윤성우의 열혈 자료구조"책을 참고해보니, 그냥 원래대로 가장 왼쪽 값을 pivot으로 하기 위해서는 pivot값을 세 수중의 중간 값으로 정하면 그 값을 맨 왼쪽 값과 swap하면 된다!