K번째 수

• 원래 의도대로라면 O(n)의 선택 알고리즘을 사용해서 풀어야 하는 문제.
• 그러나, 선택 알고리즘 에서 적었듯이, CPython3에서는 대부분의 경우 내장 sort를 이용해서 전체를 정렬하는것이 더 효율적이다.
  • 제출되어있는 대부분의 파이썬 솔루션은 내장 sort를 이용해서 풀었다
• 이 문제처럼 n이 최대 5,000,000 이라면 quickselect를 구현한 nth_element를 사용하는 것이 좀 더 빠르기는 하다.

"""Solution code for "BOJ 11004. K번째 수".

- Problem link: https://www.acmicpc.net/problem/11004
- Solution link: http://www.teferi.net/ps/problems/boj/11004
"""


from teflib import algorithm


def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    print(algorithm.nth_element(A, K))


if __name__ == '__main__':
    main()

• Dependency: teflib.algorithm.nth_element