인사고과

링크

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

문제

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

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

풀이

존재하는 모든 사원에 대해서 비교가 들어가면 이 문제는 시간초과가 걸릴 가능성이 매우 높아진다.

따라서 줄일 수 있는 사람은 최대한 제외시키고 인사고과에 대해서 비교가 진행되야한다.

문제에서 전체 사원의 점수 합에 대해서 석차를 알고 싶어하기 때문에 완호보다 점수의 합이 낮은 사람은 제외를 시켜버린다. 완호보다 높거나 같은 점수를 가진 사람으로 걸러내고, scores 배열의 구성에서 완호와 같은 점수를 가진 사람은 여러 명 나올 수 있지만, 그 사람들 중에서 완호가 가장 맨 앞에 위치하기 때문에 sort를 해도 완호가 가장 앞에 위치한다. 따라서 동석차에 대해서 고민할 필요없이 완호보다 점수가 낮은 사람은 모두 배열에서 제외를 시켜버린다.

이후 문제에서 원하는 바를 만족하기 위해 두 점수를 비교해서 낮은 경우가 나오면 제외시켜서 코드를 완성한다.

코드

function solution(scores) {
    
    const ho = scores[0]
    
    // 1. 점수의 합계가 완호보다 작다면 제외, 석차에서 어차피 계산되지 않음.
    //    반복문은 뒤에서 부터 계산, 앞에서부터 계산 시 반복문의 변수가 꼬임 
    const sum = scores[0][0] + scores[0][1]
    for(let i = scores.length - 1; i >= 0; i--) {
        const score = scores[i]
        if(score[0] + score[1] < sum) {
            scores.splice(i, 1)
        }
    }
    
    // 2. 점수의 합 순서대로 sort, 내림차순
    scores = scores.sort((a, b) => (b[0] + b[1]) - (a[0] + a[1]))
    
    // 3. 현재 완호의 인덱스 위치를 탐색, 뒤의 내용들은 모두 날리기
    const index = scores.indexOf(ho)
    scores.slice(0, index + 1)
    
    // 4. 배열에서 완호부터 맨 앞까지 반복문을 진행
    //    앞으로 이동하며 인사고과 탈락 조건에 맞는 경우를 찾기
    //    조건에 맞으면 해당 인덱스 삭제
    for(let i = index; i >= 0; i--) {
        const score = scores[i]
        for(let j = i - 1; j >= 0; j--) {
            const compare = scores[j]
            if(score[0] < compare[0] && score[1] < compare[1]) {
                scores.splice(i, 1)
                break
            }
        }
    }
    
    // 5. 완호의 값이 존재하면 해당 인덱스 + 1, 없다면 -1을 반환
    return scores.indexOf(ho) === -1 ? -1 : scores.indexOf(ho) + 1
}

리팩토링

코드 실행에는 문제 없지만, 실행시간이 6800 이상 걸리는 문제가 존재해서 최대한 실행 시간을 줄여보았다. 1번에서 완호보다 점수가 낮은 사원을 걸러낼 때, 반복문에서 확인하며 splice 함수로 잘라냈는데, filter 함수를 통해서 더 짧고 간단하게 조건에 맞지 않는 사원을 걸러냈다. 확인결과 코드 실행 시간이 최대 4500까지 줄어드는 결과를 보였다.

완호의 점수와 같은 사람도 삭제하고, 완호의 점수만 따로 추가하여 코드를 구성해보았는데 내 생각에는 동 점수의 사람도 사라져서 sort와 for문에서 splice 사용에 할당되는 시간이 더 줄어들거라 생각했는데 실제 실행 시간에서 6000까지 실행시간이 증가하는 문제를 보였다.

function solution(scores) {
    
    const ho = scores[0]
    
    // 1. 점수의 합계가 완호보다 작다면 제외, 석차에서 어차피 계산되지 않음.
    //    반복문은 뒤에서 부터 계산, 앞에서부터 계산 시 반복문의 변수가 꼬임 
    //    filter 함수로 완호보다 점수 낮은 사원은 모두 삭제
    scores = scores.filter(el => el[0] + el[1] >= ho[0] + ho[1])
    
    // 2. 점수의 합 순서대로 sort
    scores = scores.sort((a, b) => (b[0] + b[1]) - (a[0] + a[1]))
    
    // 3. 현재 완호의 인덱스 위치를 탐색, 뒤의 내용들은 모두 날리기
    const index = scores.indexOf(ho)
    scores.slice(0, index + 1)
    
    // 4. 배열에서 완호부터 맨 앞까지 반복문을 진행
    //    앞으로 이동하며 조건에 맞는 경우를 찾기
    //    조건에 맞으면 해당 인덱스 삭제
    for(let i = index; i >= 0; i--) {
        const score = scores[i]
        for(let j = i - 1; j >= 0; j--) {
            const compare = scores[j]
            if(score[0] < compare[0] && score[1] < compare[1]) {
                scores.splice(i, 1)
                break
            }
        }
    }
    
    // 5. 완호의 값이 존재하면 해당 인덱스 + 1, 없다면 -1을 반환
    return scores.indexOf(ho) === -1 ? -1 : scores.indexOf(ho) + 1
}

리팩토링 아이디어로는 이론 상 점수의 합이 같다면 서로의 인사고과에 영향을 끼치지 않는다.

즉 인사고과에 영향을 끼치는 경우는 자신의 점수 합 보다 2점 이상 높아야한다. 따라서 이 내용을 알고리즘에 포함시킨다면 좀 더 빠른 결과를 볼 수 있을 것이다.