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

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

프로그래머스

Status : Solved

Time : 00:27:15

 

---

 

문제 설명

 

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

각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.

 

입력 및 출력

 

제한사항

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

 

입출력 예

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

 

 

---

 

풀이

어제 풀이했던 문제(

2023.01.20 - [알고리즘 문제/프로그래머스] - [프로그래머스] 시소 짝꿍 (Python)

[프로그래머스] 시소 짝꿍 (Python)

)처럼, 이중 for문 등으로 해결할 수 없는 문제이다. N의 최대 개수가 100,000개까지 될 수 있기 때문. 따라서 다른 접근 방식이 필요해진다. 또한 인센티브 자격의 존재 역시 고려해야하는데, 한 사람이 임의의 다른 사람보다 두 개의 점수 모두가 낮으면 순위에서 배제해야 하기 때문이다.

얼핏 보면 "어떻게 해결하지?" 싶지만, 의외로 해답은 간단하다. 먼저 scores 리스트를 정렬하되, 점수 a를 기준으로 내림차순, 점수 b를 기준으로 오름차순으로 정렬한다. a가 높은 쪽이 앞에 오고, 같은 a일때는 b가 낮은 쪽이 앞에 온다.

그리고 우리는 어떤 사람의 인사고과 점수 (a', b')를 고려할 때, 순위에서 배제되지 않은 직전의 점수 (pa, pb)를 고려할 것이다. 앞선 정렬 조건 때문에 다음과 같은 세 가지 경우가 성립한다.

1. pa > a' 인 경우 : a'보다 앞에 오는 점수 pa는 a'와 같거나, a'보다 크게 된다. a'보다 큰 경우를 우선 생각해 보자. 앞선 정렬 조건 때문에 pb는 첫 번째 점수가 pa인 사람들 중 가장 b점수가 높은 사람이 된다.
   1. pb > b'인 경우 : 이어서, 현재 인사고과 점수 b'는 a점수가 a'인 사람들 중 가장 b점수가 낮은 사람이다. 이 사람이 직전의 점수 pb보다 낮다면, 인센티브 대상에서 무조건 제외된다 (양 쪽 점수가 높은 사람이 최소 한 명이 존재하게 되므로). 따라서 이 사람을 고려하지 않고 넘어가며, 직전의 점수 pa, pb는 그대로 유지된다. 만약 완호의 점수가 이에 해당한다면 -1을 출력해야 한다.
   2. pb <= b'인 경우 : 반대의 경우를 생각해 볼 수 있다. b'점수가 pb와 같거나 높다는 뜻은, 이 사람을 포함하여 a점수가 a'인 사람들 모두 인센티브에서 제외되지 않는다는 것을 의미한다. b'점수가 최소였으므로 모든 사람들이 pb 보다 크거나 같은 점수를 가짐이 보장되기 때문이다. 따라서 이 사람은 순위에 고려해야 한다. 추가로 완호의 점수의 합과 이 사람의 점수를 비교하여, 만약 이 사람의 점수가 높다면 등수를 1 증가시킨다(완호 앞에 있는 사람의 수를 세어야 한다). 마지막으로 직전 점수 pa, pb를 a', b'로 업데이트한다.
2. pa = a'인 경우 : 동률인 경우는 무조건 인센티브 대상에 포함되므로, 1-2와 같이 처리한다.

이런 식으로 한 번의 순회 후에 완호의 순위를 알 수 있게 된다. 정렬에 드는 시간복잡도에 좌우되므로 시간 초과 없이 문제를 통과할 수 있다. 사고력을 필요로 하는 문제였던 것 같다.

 

풀이 코드

def solution(scores):
    ta, tb = scores[0]
    scores.sort(key = lambda x : (-x[0], x[1]))
    
    pa, pb = -1, -1
    answer = 1
    for a, b in scores :
        if pa > a and pb > b :
            if (a, b) == (ta, tb) :
                return -1
            continue
        if a + b > ta + tb :
            answer += 1
        pa, pb = a, b
    
    return answer

풀이 완료!