[알고리즘] 커트라인 - 구현

문제 링크

 

커트라인 : https://www.acmicpc.net/problem/25305

 

문제탐색

기본 원리 탐색

●  N명의 응시자 중 상위 k명에게 상을주며 그 커트라인을 구하는 것은,

성적이 높은순으로 정렬하여 k 번째 점수를 출력하는 것과 같습니다.

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• 최대 학생수 : 1000명 
  • 시간복잡도가 O(n log n) 인 정렬 알고리즘은 약  3000회의 연산을 수행하므로 정렬을 사용하는데 지장이 없습니다.

=> 그러므로 python 정렬함수인 sorted를 사용하기러 합니다.

 

 

코드설계하기

1. 성적을 리스트에 입력받습니다. 단, 한줄에 공백을 기준으로 입력되므로 map함수를 활용합니다.
2. 리스트를 내림차순 정렬합니다.
3. 리스트의 k-1번째 항목을 출력합니다.

 

시도회차 수정사항

 

정답코드

n,k=input().split()
n,k=int(n),int(k)

score = list(map(lambda x: int(x),input().split())) # 공백기준으로 잘라 리스트에 int형으로 입력

score=sorted(score,reverse=True) # 내림차순 정렬

print(score[k-1]) # 커트라인 점수 출력