인사고과 (performanceEval.py)
[문제]
완호네 회사는 연말마다 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 |
[입출력 예에 대한 설명]
입출력 예 #1
5 번째 사원은 3 번째 또는 4 번째 사원보다 근무 태도 점수와 동료 평가 점수가 모두 낮기 때문에 인센티브를 받을 수 없습니다.
2 번째 사원, 3 번째 사원, 4 번째 사원은 두 점수의 합이 5 점으로 최고점이므로 1 등입니다. 1 등이 세 명이므로 2 등과 3 등은 없고 1 번째 사원인 완호는 두 점수의 합이 4 점으로 4 등입니다.
풀이
1차시도
나의 로직
- 2중 포문으로 돌면서 인센티브 못받는 사람을 걸러낸다.
- 거르면서 동시에 인센티브를 받는 사람의 배열을 만든다.
- [점수 합, 인덱스] 형태의 배열이 저장된 winners배열을 만듬.
- winners 배열을 돌면서 순위를 매긴다. total이라는 변수를 사용하여 동차 인원수를 고려한다.
코드
def solution(scores):
answer = 0
winners = []
# 인센티브 못받는 사람 필터링
for i in range(len(scores)):
flag = True
for other in scores:
if scores[i][0] < other[0] and scores[i][1] < other[1]:
if i == 0:
answer = -1
return answer
flag = False
if (flag):
winners.append([scores[i][0] + scores[i][1], i])
# 합에 따라 sort 하기
winners.sort(key=lambda x : (-x[0]))
# 첫 1위 순위 지정
winners[0].append(1)
if winners[0][1] == 0:
return 1
# 2 번째 부터 순위 계산
total = 1 # 동차 인원 수
for i in range(1, len(winners)):
if winners[i][0] < winners[i-1][0]:
winners[i].append(total + winners[i-1][2])
total = 1
else:
winners[i].append(winners[i-1][2])
total += 1
if winners[i][1] == 0:
answer = winners[i][2]
return answer
return answer결과
테스트 1 〉 통과 (0.01ms, 10.4MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.01ms, 10.2MB)
테스트 4 〉 통과 (0.01ms, 10.2MB)
테스트 5 〉 통과 (0.02ms, 10.2MB)
테스트 6 〉 통과 (0.00ms, 10.3MB)
테스트 7 〉 통과 (0.06ms, 10.2MB)
테스트 8 〉 통과 (0.11ms, 10.2MB)
테스트 9 〉 통과 (0.01ms, 10.3MB)
테스트 10 〉통과 (1.37ms, 10.2MB)
테스트 11 〉통과 (26.42ms, 10.2MB)
테스트 12 〉통과 (26.49ms, 10.2MB)
테스트 13 〉통과 (0.02ms, 10.1MB)
테스트 14 〉통과 (112.06ms, 10.4MB)
테스트 15 〉통과 (0.15ms, 10.5MB)
테스트 16 〉통과 (2691.70ms, 10.6MB)
테스트 17 〉실패 (시간 초과)
테스트 18 〉실패 (시간 초과)
테스트 19 〉통과 (0.40ms, 17.4MB)
테스트 20 〉통과 (0.91ms, 17.7MB)
테스트 21 〉실패 (시간 초과)
테스트 22 〉실패 (시간 초과)
테스트 23 〉통과 (6.10ms, 25.2MB)
테스트 24 〉실패 (시간 초과)
테스트 25 〉실패 (시간 초과)
아무래도 처음에 걸러낼 때 시간이 많이 소요되는 것 같다. 데이터 수가 10만이니 O(n^2)는 정말 오래걸리는 것 같다.
