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

프로그래머스 - 인사고과

문제설명

def solution(scores: List[List[int]]) -> int:
        ...

scores	result
[[2,2],[1,4],[3,2],[3,2],[2,1]]	4

사원들의 태도 점수와 평가 점수가 [[2,2],[1,4],[3,2],[3,2],[2,1]] 처럼 한 쌍의 정수로 이루어진 배열로 입력된다. 임의의 사원보다 두 점수가 모두 낮은 경우가 있으면 그 사원은 제외된다. 사원들의 총점을 순서대로 나열할 때 scores[0]인 사원의 석차를 구하는 문제이다.

제한사항

• 1 ≤ scores의 길이 ≤ 100,000
• scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
  • scores[0]은 완호의 점수입니다.
  • 0 ≤ a, b ≤ 100,000
• 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.

풀이

석차에서 제외되는 사원을 구하는 방법이 까다로웠다. scores의 최대 길이가 10만개이기 때문에 매번 모든 사원을 비교할 경우 시간이 초과된다. 따라서 한 번의 정렬을 수행한 다음 순회하며 규칙에 따라 사원들을 제외시키며 완호보다 점수가 높은 사원의 수를 구했다.

scores 배열의 각 원소가 [a, b]라 할 때 a에 대해 내림차순, b에 대해 오름차순으로 정렬한다. 순회를 진행할 때 배열에서 이전 사원의 점수를 [a_1, b_1], 다음 사원의 점수를 [a_2, b_2]라고 할 때 다음 규칙이 성립된다.

• scores배열이 a에 대해 내림차순 정렬을 했기 때문에 항상 a_1 > a_2이다.

순회할 때 나타났던 가장 큰 b값보다 현재 b값이 작다면 현재 사원보다 두 점수가 모두 높은 사원이 존재하는 것이다. 따라서 배열을 순회하며 max_b를 구하면서 이 값보다 작은 b 값을 가진 사원을 제외시키면 된다.

원호의 석차를 구하는 문제이기 때문에 순회하며 원호보다 큰 총점을 받은 사원의 수를 셌다.

제출 코드

def solution(scores):
    answer = 0
    b1, b2 = scores[0]
    scores.sort(reverse=True, key=lambda x: (x[0], -x[1]))
    max_s2 = 0
    for s1, s2 in scores:
        if max_s2 > s2:
            if (s1, s2) == (b1, b2):
                return -1
            continue
        if b1 + b2 < s1 + s2:
            answer += 1
        max_s2 = max(s2, max_s2)
    return answer + 1

후기

규칙을 계속 생각하면서 코드를 작성했는데도 풀기 어려웠던 문제였다. 아래 테스트케이스를 고려했을 때 도움이됐다.

scores	result
[[2,2],[2,3],[3,2],[2,2],[2,1]]	3