문제 설명
완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다.
각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.
각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤
scores의 길이 ≤ 100,000 scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.scores[0]은 완호의 점수입니다.- 0 ≤ a, b ≤ 100,000
- 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.
입출력 예
| scores | result |
|---|---|
| [[2,2],[1,4],[3,2],[3,2],[2,1]] | 4 |
입출력 예 설명
5 번째 사원은 3 번째 또는 4 번째 사원보다 근무 태도 점수와 동료 평가 점수가 모두 낮기 때문에 인센티브를 받을 수 없습니다.
2 번째 사원, 3 번째 사원, 4 번째 사원은 두 점수의 합이 5 점으로 최고점이므로 1 등입니다. 1 등이 세 명이므로 2 등과 3 등은 없고 1 번째 사원인 완호는 두 점수의 합이 4 점으로 4 등입니다.
고민한 점
scores의 길이를N이라고 가정하자.인센티브를 받지 못하는 사람을 찾는 것은 이중 for문으로 구현할 수 있다.
하지만, 시간복잡도가 으로 시간초과가 발생할게 자명하다.
두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다.라는 키워드에서scores리스트를 정렬하면 어떨까? 라는 생각을 했다.파이썬의 내장 정렬 함수는 시간복잡도가 으로 약 160만이다.
이는 충분히 가능하다고 판단했다.
- 두 점수가 모두 낮은 경우는 어떻게 비교할까?
- 두 점수의 합이 높은 순으로 석차를 낸다는 것은,
두 점수의 합을 기준으로scores배열을 내림차순 정렬하면 되나? - 석차 계산을 할 때 어느 점수를 기준으로 해야하나?
문제에서 눈여겨 봐야할 키워드
- 어떤 사원이 다른 임의의 사원보다
두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못한다.두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급된다.- 두 점수의 합이 동일한 사원들은 동석차이며,
동석차의 수만큼 다음 석차는 건너 뛴다.
우리가 구하고자 하는 것은 완호의 등수 이다.
그렇다면 완호의 등수는 어떻게 구할 수 있을까?
예를 들어, 마라톤 대회에서 1등 - 2등 - 3등 - 4등 - 5등 ... 이렇게 있다고 가정하자.
4등은 어떻게 해서 4등이 되는걸까? → 4등 앞에 3명이 있기 때문이다.
(4등의 완주 시간보다 더 이른 완주를 한 사람이 3명이나 있다는 것이다.)
즉, x의 등수 를 구하려면, x보다 점수가 높은 사람 이 몇 명이나 있는지 확인하면 된다.
이 문제에서는 완호의 등수를 구해야하므로,
완호의 두 점수의 합 보다 큰 점수를 가지는 사람 이 몇 명이나 있는지 확인하면 된다.
✅ 즉, 등수 비교 를 완호의 점수를 기준 으로 수행해야 한다는 의미이다.
처음 접근
def solution(scores):
wanho = scores[0] # 완호 점수
scores.sort(key=lambda x: sum(x), reverse=True) # 근무 태도 점수 + 동료 평가 점수 합으로 내림차순 정렬
same_count = 1 # 동일 등수
prev = 0 # 이전 점수
rank = 1 # 원호의 등수
# 점수를 순회하면서
for score in scores:
if prev == sum(score): # 이전 점수가 현재 점수와 같다면, 즉 동일 등수
same_count += 1 # 동일 등수를 1 증가
else: # 같지 않다면
if score == wanho: # 만약, 원호의 점수라면
rank += same_count # 동일 등수만큼 등수를 증가 -> 원호의 등수 get
break
prev = sum(score) # 이전 점수 갱신(동일 등수인지 파악하기 위해)
# 원호가 임의의 사원의 점수보다 모두 낮은 점수를 가지고 있다면
for score in scores:
if score != wanho: # 완호 자기 자신이 아닐 때
if wanho[0] < score[0] and wanho[1] < score[1]:
return -1 # -1 반환
return rank- 첫 번째 for문에서 인센티브를 받지 못하는 사람을 고려했어야 하는데 하지 않음
- 등수 계산을 원호 기준이 아닌 처음 사람부터 무작정 계산
- scores배열을 두 점수의 합을 기준으로 내림차순 정렬함 → 인센티브 받지 못하는 사람을 찾기 힘들어짐
→ 그냥 애초에 틀려먹은 접근으로 짠 코드. 😡
# 인센티브 여부는 어떻게 비교?
# -> 근무 태도 점수, 동료 평가 점수가 임의의 사원의 점수보다 모두 낮다면
def solution(scores):
rank = 1 # 완호의 등수
wanho = scores[0] # 완호의 점수(근무 태도, 동료 평가)
wanho_sum = sum(sores[0]) # 완호의 두 점수 합
prev = 0 # 이전 동료 평가 점수
# 근무 태도 내림차순, 동료 평가 오름차순
# 이렇게 되면, 동료 평가 점수만으로 인센티브 지급 여부를 판단할 수 있다.
scores.sort(key=lambda x: (-x[0], x[1]))
# 완호의 점수를 기준으로 점수를 확인하면서
for score in scores:
# 완호가 인센티브를 받을 수 없다면
if wanho[0] < score[0] and wanho[1] < score[1]:
return -1
# 현재 동료 평가 점수가 앞선 동료 평가 점수보다 클 때만
# (작다면 인센티브 받지 못하는 것)
if prev <= score[1]:
# 현재 점수 합이 완호의 두 점수 합보다 크다면
if wanho_sum < sum(score):
rank += 1 # 등수 올린다.
prev = score[1] # 갱신 (prev는 항상 최댓값을 가진다)
return rank-
scores를 정렬할 때, 두 점수의 합으로 정렬하면 안된다.
- 인센티브 지급 여부 판단이 힘들거나 안된다.
- 따라서, 근무 태도 기준으로 내림차순 정렬을 하고,
근무 태도 점수가 같다면 동료 평가 기준으로 오름차순 정렬을 한다. - 이렇게 하면, 인센티브 지급 여부를 판단할 때 근무 태도는 보지 않고, 동료 평가 점수로만 계산할 수 있다. → 으로 계산 가능
-
등수 정할 때 완호의 점수를 기준으로 삼아야 한다.
- 위에서 언급했듯이, 구하고자 하는 것이 완호의 등수이다.
완호의 등수를 결정짓는 것은,'완호보다 앞선 등수가 몇 명이 있는지'이다.
- 위에서 언급했듯이, 구하고자 하는 것이 완호의 등수이다.
