프로그래머스 - 인사고과 (JavaScript)

문제

완호네 회사는 연말마다 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 합니다.

 

생각해보기

완호보다 점수의 합이 높은 사원 중 인센티브를 받지 못하는 사원을 제외하는 것이 이 문제의 핵심이다. 모든 사원들에 대해 탐색을 수행하면 O(n^2)으로 시간 초과가 발생한다.

 

근무 태도 점수와 동료 평가 점수의 대소관계 비교를 통해 인센티브를 받지 못하는 사원을 정한다. 즉, 근무 태도 점수와 동료 평가 점수를 기준으로 정렬하여 이를 비교할 수 있다. 정렬의 경우 O(nlogn)이며, 이를 통해 탐색은 O(n)이 된다.

 

근무 태도 점수를 기준으로 내림차순 정렬이 되면, 동료 평가 점수로 인센티브 여부를 판별할 수 있다. 즉, 이전 사원들의 동료 평가 점수의 최대값보다 커야 인센티브를 받을 수 있다.

 

단, 같은 근무 태도 점수를 가지는 사원들은 동료 평가 점수를 기준으로 오름차순 정렬해야 한다. 같은 근무 태도 점수를 가지는 사원들 간의 비교에서 동료 평가 점수가 낮아 인센티브를 받지 못하는 경우로 판별되는 잘못된 케이스가 나올 수 있기 때문이다.

 

풀이

function solution(scores) {
    var answer = 1;
    const wanho = scores[0];

    scores.sort((a, b) => {
        if (a[0] == b[0]) {
            return a[1] - b[1];
        }
        return b[0] - a[0]});
    
    let before = 0;
    for (const score of scores) {
        if (wanho[0] < score[0] && wanho[1] < score[1]) {
            return -1;
        }
        if (before <= score[1]) {
            if (wanho[0] + wanho[1] < score[0] + score[1]) {
                answer += 1;
            }
            before = score[1];
        }
    }
    return answer;
}