사용자 도구

사이트 도구


ps:problems:boj:11004

K번째 수

ps
링크acmicpc.net/…
출처BOJ
문제 번호11004
문제명K번째 수
레벨실버 5
분류

선택 알고리즘

시간복잡도O(n)
인풋사이즈n<=5,000,000
사용한 언어Python
제출기록623580KB / 2848ms
최고기록3692ms
해결날짜2020/12/21

풀이

  • 원래 의도대로라면 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()

토론

댓글을 입력하세요:
A G G D E
 
ps/problems/boj/11004.txt · 마지막으로 수정됨: 2021/01/03 17:21 저자 teferi