[Programmers Lv.3] 인사고과 - Python

문제

완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.
각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.

 

쉽게 풀릴 줄 알고 밤에 가벼운 마음으로 시작했다가 생각보다 오래 걸린 문제였다...

 

처음에는 사원들의 총 점수를 기준으로 내림차순 정렬 해서 순회하며 완호보다 두 점수가 모두 높은 사원이 있다면 -1을 리턴하고, 없다면 완호보다 높은 점수를 가진 사원의 수를 return했다.

내가 생각하지 못했던 점은 완호보다 총 점수가 높은 사람이어도 인센티브 대상이 아닐 수 있다는 점이었다. 

처음에 내림차순 정렬했던 방식에서 벗어나지 못하고 각 사원의 인센티브 대상 여부를 모두 먼저 검사하려다가 시간 초과가 났다.

 

총 점수를 기준으로 정렬하지 않고 다른 사원의 인센티브 대상 여부를 더 효율적으로 판단할 방법을 고민했다.

첫 번째 점수를 기준으로 내림차순 정렬하면 뒤의 사원은 앞의 사원보다 첫 번째 점수가 항상 낮다. 따라서 두 번째 점수까지 낮다면 인센티브 대상이 아니므로, 완호의 앞 순위에 카운팅하지 않아도 된다. 정렬을 통해 모든 사원들 간의 비교를 하지 않아도 되도록 하는 것이다.

이를 위해 두 번째 점수는 오름차순으로 정렬했다. 이전 인센티브 대상자보다 두 번째 점수가 낮다면 인센티브 대상이 아닌 것으로 판단한다. 예를 들어 [3, 1], [3,4], [2, 3], [1, 2]와 같은 상황에서 마지막 두 사원은 인센티브 대상이 아니다. 이전 인센티브 대상자들의 두 번째 점수 최댓값을 업데이트하며 구현했다.

코드

def solution(scores):
    answer = 1
    wa, wb = scores[0]
    wscore = wa + wb
    scores.sort(key = lambda x:(-x[0], x[1]))
    prevb = 0
    for a, b in scores:
        if a > wa and b > wb:
            return -1
        if b >= prevb:
            prevb = b
            if a + b > wscore:
                answer += 1
    return answer

 

처음에 작성했던 코드보다 양이 반으로 줄었다.

코테 문제를 풀 때 코드가 길어지고 depth가 3 이상으로 늘어나면, 특히 이중 for문을 남발하는 상황이 됐다면 내 풀이 방식을 먼저 의심해 봐야 할 것 같다.