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

문제 설명

연말 인사고과에 따라 인센티브를 지급하는 회사에서, 각 사원의 근무 태도 점수와 동료 평가 점수를 바탕으로 석차를 계산합니다.

• 어떤 사원이 다른 사원에 비해 두 점수 모두 낮다면, 그 사원은 인센티브를 받을 수 없습니다.
• 인센티브 대상인 사원들의 경우, 두 점수의 합으로 석차를 결정하며, 동점인 경우 같은 석차로 처리합니다.
• 주어진 점수 목록에서 완호의 석차를 계산하여 반환합니다.
• 만약 완호가 인센티브를 받지 못하는 경우 -1을 반환합니다.

---

제한 사항

1. 1 ≤ scores의 길이 ≤ 100,000
2. scores의 각 행은 [a, b] 형태로, 근무 태도 점수 a와 동료 평가 점수 b를 나타냅니다.
3. scores[0]은 완호의 점수입니다.
4. 0 ≤ a, b ≤ 100,000
5. 결과적으로 완호가 인센티브를 받지 못하는 경우 -1을 반환해야 합니다.

---

해결 방법

알고리즘: 정렬 및 그리디

1. 사전 정렬
   • 근무 태도 점수(a)를 기준으로 내림차순 정렬합니다.
   • 같은 점수일 경우 동료 평가 점수(b)를 기준으로 오름차순 정렬합니다.
   • 이를 통해 특정 사원의 점수가 다른 사원보다 모두 낮은지를 효율적으로 검증할 수 있습니다.
2. 인센티브 대상 검증
   • 순회하면서 현재까지의 최대 동료 평가 점수를 저장합니다.
   • 만약 현재 사원의 동료 평가 점수가 이 최대값보다 작다면, 해당 사원은 인센티브를 받을 수 없습니다.
   • 이 과정에서 완호가 인센티브 대상에서 제외되는 경우 바로 -1을 반환합니다.
3. 완호의 석차 계산
   • 유효한 점수(인센티브 대상)의 합을 계산하여 리스트에 저장합니다.
   • 이 합을 기준으로 내림차순 정렬 후, 완호의 점수 합과 일치하는 지점에서 석차를 반환합니다.

---

시간 복잡도

1. 정렬: O(nlog⁡n)
   • scores를 조건에 따라 정렬하는 데 소요됩니다.
2. 검증 및 석차 계산: O(n)
   • 리스트를 순회하며 인센티브 대상을 검증하고, 석차를 계산합니다.

총 시간 복잡도: O(nlog⁡n)

---

구현 코드

function solution(scores) {
  const userScore = scores[0];
  const userSum = userScore[0] + userScore[1];
  let maxPeer = 0;
  let answer = 1;

  scores.sort((a, b) => b[0] - a[0] || a[1] - b[1]);

  const validScores = [];
  for (const [attitude, peer] of scores) {
    if (peer < maxPeer) {
      if (attitude === userScore[0] && peer === userScore[1]) {
        return -1;
      }
    } else {
      maxPeer = Math.max(maxPeer, peer);
      validScores.push(attitude + peer);
    }
  }

  validScores.sort((a, b) => b - a);

  for (const sum of validScores) {
    if (sum === userSum) break;
    ++answer;
  }

  return answer;
}