[프로그래머스] 인사고과 (Python)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/152995

프로그래머스

---

풀이

일단 1 ≤ scores의 길이 ≤ 100,000의 제한이 있기 때문에 O(n^2)으로 한 사원마다 모든 사원을 비교해 풀게 되면 시간 초과가 발생한다. 그렇기 때문에 O(n)으로 풀어주어야 한다. 문제에서 중요한 조건 중 하나가 "어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브 받지 못한다." 라는 것이다. 일단 근무 태도 점수를 A, 동료 평가 점수를 B라고 가정하자. 그리고 이 조건을 해결하기 위해 A를 내림차순, B를 오름차순으로 정렬한다.

Ex) [4, 4], [6, 2], [7, 3], [7, 4], [8, 2], [9, 1], [9, 4]

--> [9, 1], [9, 4], [8, 2], [7, 3], [7, 4], [6, 2], [4, 4]

 

위와 같이 정렬한 이유는 인센티브를 받지 못하는 사원을 걸러내기 위해서이다. 내림차순으로 정렬했을때 A는 항상 작거나 같기 때문에 B만 비교를 해주면 된다. 첫 top_score는 정렬 후 첫번째 인덱스이고, 현재 score의 B가 더 클 때마다 그 점수를 top_score로 초기화한다. B가 top_score보다 작을 때 인센티브를 받지 못하는 알고리즘이기 때문에 B는 오름차순으로 정렬한다.

코드

def solution(scores):
    rank = 1
    my_score = scores[0]
    scores.sort(key=lambda x: (-x[0], x[1]))
    top_score = scores[0]
    
    for i in range(len(scores)):
        if my_score[0]<top_score[0] and my_score[1]<top_score[1]:
            return -1
                
        if scores[i][1]>=top_score[1]:
            if sum(scores[i])>sum(my_score):
                rank += 1
                
            top_score = scores[i]
        
    return rank