BOJ 25305번: 커트라인

핵심 포인트

• 정렬 알고리즘

제출코드

N, k = map(int, input().split())
numbers = list(map(int, input().split()))
for i in range(1, N):
  key = numbers[i]

  for j in range(i-1, -1, -1):
    if numbers[j] > key: numbers[j+1] = numbers[j]
    else:
      j += 1
      break

  numbers[j] = key
print(numbers[-k])

해설

지난 포스팅의 BOJ 2750번: 수 정렬하기의 삽입정렬을 그대로 이용하여 문제를 풀 수 있습니다. 삽입정렬에 대한 자세한 알고리즘은 지난 포스팅을 참고해주시길 바랍니다. 여기서 주의할 점은 오름차순으로 정렬되어 있기 때문에 큰 숫자는 뒤에 있습니다. 따라서, 파이썬의 음수 인덱싱을 활용하여 뒤에 있는 큰 값 인덱스부터 접근할 수 있습니다. 이때, 커트라인은 단순히 내림차순 기준 k번째 점수이므로 numbers[-k]를 출력하면 됩니다. 

 

 

참고자료 및 그림출처

백준 코딩 문제