[Python] 프로그래머스 Lv3. 인사고과

문제

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

프로그래머스

 

문제 요약

각 사원은 근무 태도 점수와 동료 평가 점수를 가진다.
어떤 사원이 다른 사원보다 두 점수가 모두 낮으면 인센티브 대상에서 제외된다.
인센티브를 받을 수 있는 사원들은 두 점수의 합을 기준으로 순위를 정한다.

scores[0]에 해당하는 완호가 인센티브를 받을 수 없다면 -1.
받을 수 있다면 완호의 석차를 반환하면 된다.

---

풀이

모든 사원을 서로 비교하면 시간이 오래 걸리기 때문에 점수를 정렬한 뒤 한 번만 순회한다.

먼저 첫 번째 점수는 내림차순,
두 번째 점수는 오름차순으로 정렬한다.

scores.sort(key=lambda x: (-x[0], x[1]))

첫 번째 점수가 높은 사원부터 확인하기 때문에 지금까지 확인한 사원 중 두 번째 점수의 최댓값만 저장하면 된다.

 

현재 사원의 두 번째 점수가 max_score보다 작다면 앞에서 이미 확인한 사원 중
- 첫 번째 점수도 더 높고
- 두 번째 점수도 더 높은
사원이 존재한다는 뜻이므로 인센티브 대상에서 제외한다.

if b < max_score:
    if [a, b] == wanho:
        return -1
    continue

여기서 첫 번째 점수가 같은 경우에는 서로를 탈락시킬 수 없기 때문에, 두 번째 점수를 오름차순으로 정렬하는 것이 중요하다.

인센티브 대상인 사원 중 완호보다 점수의 합이 큰 사람이 있을 때마다 rank를 1씩 증가시키면 완호의 최종 순위를 구할 수 있다.

def solution(scores):
    wanho = scores[0]
    wanho_sum = sum(wanho)

    scores.sort(key=lambda x: (-x[0], x[1]))

    max_score = 0
    rank = 1

    for a, b in scores:
        if b < max_score:
            if [a, b] == wanho:
                return -1
            continue

        max_score = max(max_score, b)

        if a + b > wanho_sum:
            rank += 1

    return rank

시간복잡도

사원 수를 n이라고 하면 정렬에 O(n log n), 이후 모든 사원을 한 번 확인하는 데 O(n)이 걸린다.
따라서 전체 시간복잡도는 O(n log n)이다.