문제 개요
길이가 n인 숫자 리스트 nums가 주어져 있다고 가정해 보겠습니다. 이 리스트의 각 요소는 수영 대회 참가 선수들의 현재 점수를 나타냅니다. 마지막 결승에서는 이번 라운드의 1위 선수가 n점, 2위 선수가 n-1점을 받는 식으로 순위에 따라 점수가 차등 지급됩니다. 우리가 구해야 할 값은 현재 라운드가 끝난 후, 결승이 종료되었을 때 여전히 우승할 수 있는 선수가 몇 명인지입니다. 단, 최고 점수가 동률인 경우에도 우승으로 간주합니다.
예제로 이해하기
입력이 nums = [9, 6, 11, 12]라고 해봅시다. 이때 정답은 3입니다. 현재 점수가 9점, 11점, 12점인 세 선수는 결승 결과가 [13, 9, 13, 13]이 되도록 순위가 정해지면 모두 공동 우승을 차지할 수 있기 때문입니다.
- 9점 선수가 1위를 하면 4점을 추가로 얻어 최종 13점이 됩니다.
- 6점 선수가 2위를 하면 3점을 얻어 최종 9점이 됩니다.
- 11점 선수가 3위를 하면 2점을 얻어 최종 13점이 됩니다.
- 12점 선수가 4위를 하면 1점을 얻어 최종 13점이 됩니다.
반면 6점 선수는 어떤 경우에도 우승할 수 없습니다. 예를 들어 6점 선수가 1위를 하면 최종 점수는 10점에 불과하고, 9점 선수가 2위를 하면 12점이 됩니다. 이처럼 가능한 모든 순위 조합을 고려해 봐도 그 선수가 최고 점수에 오르는 경우는 존재하지 않습니다.
풀이 접근 방법
다음 단계를 따라 문제를 해결할 수 있습니다.
- nums가 비어 있으면 0을 반환합니다.
- n := nums의 크기
- ans := 0
- 리스트 nums를 오름차순으로 정렬합니다.
- a := 0
- i를 n-1부터 0까지 1씩 줄여 가며 반복합니다.
- cand := nums[i] + n - i
- cand > a이면 a := cand로 갱신합니다.
- nums의 모든 요소 x에 대해 반복합니다.
- x + n >= a이면 ans를 1 증가시킵니다.
- ans를 반환합니다.
핵심 아이디어
여기서 변수 a는 결승에서 1위가 기록하게 될 '가장 낮은 우승 점수', 즉 우승 커트라인을 의미합니다. 순위가 어떻게 배정되더라도 최종 최고 점수는 a 미만이 될 수 없으며, 반대로 순위를 적절히 배분하면 최고 점수를 정확히 a로 만들 수 있습니다. 따라서 어떤 선수의 현재 점수가 x일 때, 1위 보너스인 n점을 모두 받는 가장 유리한 상황에서조차 x + n이 a에 미치지 못한다면 그 선수의 우승은 불가능합니다. 반대로 x + n >= a라면 최소한 공동 우승은 가능하므로 우승 가능 선수로 집계합니다.
구현 예제
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(nums):
if not nums:
return 0
n = len(nums)
ans = 0
nums.sort()
a = 0
for i in range(n - 1, -1, -1):
cand = nums[i] + n - i
if cand > a:
a = cand
for x in nums:
if x + n >= a:
ans += 1
return ans
nums = [9, 6, 11, 12]
print(solve(nums))
입력
[9, 6, 11, 12]
출력
3