파이썬 Python | 알고리즘 | 백준 커트라인

 

⭕ 파이썬 Python | 알고리즘 | 백준 커트라인

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 구현 문제로 분류되어 있다. 구현 문제란 문제의 조건을 코드로 직접 구현해야 하는 유형을 말한다. 구현 문제는 구현을 해야 하는...?
• n명의 학생 점수가 주어지고, 상위 k명까지 상을 받는다.
• 즉, 점수를 내림차순으로 정렬하여 k번째 점수를 출력하면 된다.

 

➡️ 코드 설계하기

• 입력을 읽어 들인다. 입력은 첫 줄에 n과 k, 다음 줄에 각 학생의 점수로 주어진다.
  • input().split()을 통해 공백을 기준으로 데이터를 나누고, 첫 번째와 두 번째 요소를 각각 N과 k로 변환한다.
  • 나머지 데이터를 scores 리스트에 정수형으로 변환하여 저장한다.
• 점수를 리스트에 저장한 후 내림차순으로 정렬한다. 리스트의 정렬은 시간복잡도가 O(NlogN)이다. N값의 범위는 1 <=N <=1000이므로 최대 약 3000개의 연산이 필요하다.
• 정렬된 리스트에서 k번째 점수를 출력한다. 

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차

• 점수를 오름차순으로 정렬하였다. 하지만 문제에서 요구하는 것은 내림차순 정렬이다. sort()는 기본적으로 오름차순으로 정렬된다. 따라서 상위 k번째 점수를 올바르게 구할 수 없다. 언어별로 내림차순 정렬을 구현하는 방법은 다르겠지만, 이런저런 syntax들을 외우기 귀찮다면 원소들에 -1을 곱해 음수화 해서 저장한 후에 정하면 된다!

import sys
    
N, k = map(int, sys.stdin.readline().split())
scores = list(map(int, sys.stdin.readline().split()))

scores.sort()
    
print(scores[k - 1])

---

2회 차

• 시간 88ms
• 내림차순 정렬로 수정하였다. 이를 위해 sort() 함수의 reverse=True 인자를 사용하였다.

import sys
    
N, k = map(int, sys.stdin.readline().split())
scores = list(map(int, sys.stdin.readline().split()))

scores.sort(reverse=True)
    
print(scores[k - 1])

 

➡️ 정답 코드

import sys
    
N, k = map(int, sys.stdin.readline().split())
scores = list(map(int, sys.stdin.readline().split()))

scores.sort(reverse=True)
    
print(scores[k - 1])