문제 링크
풀이 과정
•
직관적으로는 다음과 같이 문제를 접근하였습니다.
◦
scores 레코드를 순회하면서, 두 점수가 모두 낮은 사원을 제외시킨다
◦
남은 사원들의 점수와 완호의 점수를 비교한 다음, 완호의 최종 순위를 결정한다
•
이때, 모든 사원 간 점수를 비교하는 과정에서 이중 반복문을 사용해야 합니다.
◦
한 명의 사원 입장에서 다른 사원보다 두 점수가 모두 낮은 경우가 존재할 수 있습니다.
◦
이 때는, 점수 비교 대상에서 즉시 제외를 시켜야 합니다.
◦
하지만, scores의 최대 길이가 10^5이므로 시간 초과가 발생할 수 있습니다.
•
따라서, 조금 더 효율적인 방법을 활용하여 시간 복잡도를 줄여야합니다.
•
본 문제에서는 정렬을 통해 접근할 수 있습니다.
◦
근무 태도 점수를 기준으로 내림차순 정렬합니다.
◦
근무 태도 점수가 동일한 경우, 동료 평가 점수 기준으로 오름차순 정렬합니다.
◦
해당 정렬 방법을 적용하면, 순차 탐색으로 두 점수가 모두 낮은 사원을 찾을 수 있습니다!
▪
i 번째 사원의 동료 평가 점수가 (0~(i-1)) 번째 동료 평가 점수보다 낮은 경우 → 두 점수가 모두 낮음
◦
순차 탐색을 통해, 완호의 순위를 결정합니다.
전체 코드
def solution(scores):
if len(scores) == 1: return 1
else:
wanho_scores = scores[0]
wanho_total = sum(wanho_scores)
rank = 1 # 최종 완호 순위
scores = scores[1:]
scores = sorted(scores, key=lambda x: (-x[0], x[1]))
threshold = 0
for other_score in scores:
if (wanho_scores[0] < other_score[0]) and (wanho_scores[1] < other_score[1]):
return -1
else:
# i번째 사원의 동료 평가 점수가 (0~(i-1))번째 동료 평가 점수 이상인 경우만 고려
if other_score[1] >= threshold:
if wanho_total < sum(other_score): rank += 1
threshold = other_score[1]
return rank
Python
복사