[백준] 25305번 커트라인 Python

문제

2022 연세대학교 미래캠퍼스 슬기로운 코딩생활에 $N$명의 학생들이 응시했다.
이들 중 점수가 가장 높은 $k$명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.
커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다.

입력

첫째 줄에는 응시자의 수
$N$과 상을 받는 사람의 수
$k$가 공백을 사이에 두고 주어진다.
둘째 줄에는 각 학생의 점수
$x$가 공백을 사이에 두고 주어진다.

출력

상을 받는 커트라인을 출력하라.

제한

$1 ≤ N ≤ 1\,000$ 
$1 ≤ k ≤ N$ 
$0 ≤ x ≤ 10\,000$ 

예제 입력 1

5 2
100 76 85 93 98

예제 출력 1

98

시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다.

문제 탐색하기

상위 K명의 점수를 구해서 커트라인 즉 k명의 점수 중 가장 낮은 점수 구하기.
주어진 조건:

• 시험에 응시한 학생 수를 나타내며, 최대 1,000명까지 가능.
• 상을 받는 학생의 수를 의미하며, 전체 학생 수 N 보다 작거나 같아야 함.
• 각 학생의 점수는 0점에서 10,000점 사이.

가능한 시간복잡도

N log N의 시간복잡도를 가지기 때문에 정렬 알고리즘으로 결정.

알고리즘 선택

list에 N개의 점수를 넣어 정렬하고나서 커트라인을 출력하기 위해 인덱스에 접근해야 함.
정렬 알고리즘으로 접근해 보겠습니다.

코드 설계하기

1. 첫 줄에서 N과 k를 입력받습니다.
2. 그다음 각 학생의 점수를 입력받아 리스트에 저장합니다.
3. 순서 없이 저장된 점수들을 내림차순으로 정렬하여 제일 높은 점수가 리스트의 앞부분에 오도록 합니다.
4. 정렬된 리스트에서 k-1번째 인덱스의 점수를 커트라인으로 설정하고 출력합니다.

코드 구현

import sys

N, K = map(int, sys.stdin.readline().split())

list_ = list(map(int, sys.stdin.readline().split()))

list_.sort(reverse=True)

print(list_[K-1])