문제
- 사원별 근무 태도 점수와 동료 평가 점수가 기록된다.
- 어떤 사원이 다른 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있으면 인센티브를 받지 못한다.
- 인센티브는 두 점수의 합이 높은 순서대로 차등 지급된다.
- 동석차가 발생할 경우 동석차 수만큼 다음 석차는 건너 뛴다.
- 완호의 석차를 리턴하고, 인센티브를 받지 못하는 경우에는 -1 리턴하기
풀이
- 인센티브는 두 점수의 합이 높은 순서대로 지급되지만, 근태 점수와 동료평가 점수 2개 항목에 대한 비교가 필요하다.
- 따라서 근태점수 내림차순으로 정렬하고, 같은 경우에는 동료 평가는 오름차순으로 정렬해 비교한다.
- 순서대로 볼 때, 근태 점수가 이미 내림차순이기 때문에 동료 평가 점수가 자기 이전보다 높기만 하면 인센티브를 받을 수 있다.
- 여기서, 완호의 점수 합보다 큰 경우에는 완호보다 석차가 높다고 볼 수 있다.
- 시간 복잡도 : $O(NlogN)$
- 정렬할 때 $O(NlogN)$ 이고 점수 비교할 때 $O(N)$ 이다.
def solution(scores):
wan = scores[0] # 완호 점수
wan_sum = sum(scores[0]) # 완호 점수의 합
# 근태점수 내림차순 + 동료평가 오름차순으로 정렬
scores.sort(key=lambda x:(-x[0], x[1]))
prev = scores[0][1] # 이전 랭크의 동료평가 점수
answer = 1 # 완호보다 높은 랭크 수
for s in scores:
# 완호가 인센티브 못받는 경우
if wan[0] < s[0] and wan[1] < s[1] :
return -1
# 비교 시작 (동료 평가 점수 기준)
# 이전 랭크의 동료평가 점수보다 높고, 완호 점수 합보다 크면 완호보다 높은 랭크
if s[1] >= prev and wan_sum < sum(s):
answer += 1
prev = s[1]
return answer
References
