문제

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

풀이

시간초과

• 우선 Array.prototype.some() 함수로 완호보다 근태점수/동료평가점수 둘 다 높은 직원이 하나라도 있으면 바로 return -1 하고 끝내는 로직을 추가.
• 다른 누군가가 인센티브 대상에서 제외되는 것도 신경써줘야 하므로 Array.prototype.filter() 내부에 Array.prototype.some()을 사용해서 false를 반환하는 사람만(자신보다 두 점수 모두 높은 사람이 한 명이라도 없는 사람) 남긴다. (🚨여기서 문제.. 시간복잡도가 O(N^2)이 되어버려서 scores의 길이가 최대 100,000인 것에 따라서 시간 초과가 난다.)
• 그리고 나서 남은사람들끼리의 근태점수/동료평가점수 합산한 점수 배열을 만들고, 해당 점수 배열을 내림차순으로 정렬하였다.
• 여기에서 점수가 앞의 점수와 현재 점수가 다를 때만 current rank를 알맞게 변화시켜주었고, 완호의 등수는 완호의 점수합과 같은 점수의 인덱스를 Array.prototype.indexOf()로 구하였다.

통과한 아이디어

일단 scores의 길이가 최대 100,000이므로 무조건 O(N^2)보다는 빠르게 들어와야 한다.
따라서, 인센티브 대상이 되지 않을 사람들 '모두'를 고려해서 제외시켜 줄 필요 없이, 간단한 if문 하나로 걸러줄 수 있으면 좋겠다고 생각했다.

• 우선 scores 배열을 다음 기준에 따라서 정렬한다.
  • 근태점수를 기준으로 내림차순 정렬한다. 이때, 근태점수가 동일하면 동료평가점수를 기준으로 '오름차순' 정렬한다. (일단 인센티브는 점수합을 기준으로 산정되고, 근태점수를 기준으로 내림차순 정렬했으니, 동료평가점수가 얼만큼 크냐에 따라서 랭크가 바뀔 수 있다는 것이 포인트)
• for ... of 반복문으로 scores 배열을 순회하면서 다음 작업을 수행한다.
  • peerMax: 반복문에서 바로 직전의 사람까지를 봤을 때, 가장 높았던 동료평가점수
  • 만약, 완호의 두 점수보다 높은 사람을 만났다면 바로 return -1 해주면 된다.
  • 그렇지 않다면, rank와 peerMax에 저장된 값을 적절히 조정해준다.
    • 만약 현재 사람의 동료평가점수가 peerMax보다 크다면, peerMax를 현재 사람의 동료평가점수로 업데이트한다. 이때, 이 사람의 모든 점수의 합이 완호의 모든 점수의 합보다 크다면 완호보다 무조건 등수가 높을 것이므로 rank++ 해준다.
    • 현재 사람의 동료평가점수가 peerMax보다 크지 않은 경우는 고려하지 않는데, 왜냐면 이미 근태점수도 앞사람들보다 낮은데 동료평가점수도 역대 최대의 동료평가점수보다 낮다면 무조건 자신보다 두 점수가 높은 사람이 존재한다는 의미이기 때문이다.

코드

function solution(scores) {
    let rank = 1;
    const wanho = scores[0];
    const wanhoSum = wanho[0] + wanho[1];
    
    //scores를 정렬
    scores.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
    
    //peerMax: 반복을 돌면서 '여태까지의 동료평가점수 중 최고점수'를 의미함.
    let peerMax = 0;
    for(const s of scores) {
        //완호의 탈락조건
        if(wanho[0] < s[0] && wanho[1] < s[1]) return -1;
        
        //완호가 (아직) 탈락하지 않았을 때 완호의 등수 계산
        if(s[1] >= peerMax) {
            if(s[0] + s[1] > wanhoSum) rank ++;
            peerMax = s[1];
        }
    }
    
    return rank;
}