[백준 / python] 25305번 커트라인

오늘은 구현 유형인 백준 25305번 문제, 커트라인을 풀어보겠습니다!

 

< 문제 확인 >

https://www.acmicpc.net/problem/25305

---

📌 문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

슬기로운 코딩생활에 N명의 학생들이 응시했다.

이들 중 점수가 가장 높은 k명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.

(커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다)

 

최근에 정렬 알고리즘을 사용하는 문제를 많이 풀어서 그런지 정렬이 바로 떠오르네요 ㅎㅎ

점수가 높은 k명의 학생들 중 점수가 가장 낮은 점수를 출력하면 될 것 같은데요!

 

학생들의 점수를 입력받아 정렬 후 인덱스 번호가 k-1번인 점수를 출력해볼까요?

 

✔️ 가능한 시간복잡도

입력할 수 있는 학생수는 최대 1000명이므로

O(Nlog⁡N) 시간 복잡도를 가지는 정렬 알고리즘을 사용해도 충분할 것 같습니다!

 

✔️ 알고리즘

모든 학생들의 점수를 정렬한 후, 커트라인으로 상을 받는 학생의 점수를 출력합니다.

 

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 학생수인 N과 상을 받는 사람의 수인 k를 입력받습니다.

2. 다음으로 각 학생들의 점수 x를 리스트로 입력받습니다.

3. 점수가 저장된 리스트를 내림차순으로 정렬하고, 인덱스번호 k-1에 해당하는 점수를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

---

📌 정답 코드

N, k = map(int, input().split())
scores = list(map(int, input().split()))

scores.sort(reverse=True) # 점수를 내림차순으로 정렬
print(scores[k-1]) # 커트라인 점수 출력

이번 주 1일 1문제풀기 챌린지 완료입니다! 8월 한 달동안 힘내서 달려볼게요 ㅎㅎ

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no