프로그래머스 코딩테스트 - 인사고과

문제 설명

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

프로그래머스

 

해결 방법

기본 아이디어

• 점수 목록의 길이가 1이면 완호의 등수는 1이다.
• 완호의 인사고과 두 점수가 임의의 사원보다 낮은 경우가 한 번이라도 있다면 -1을 반환한다.

아이디어 1: 인센티브 제외 -> 정렬 -> 완호의 등수 구하기

인센티브를 받지 못하는 사람들을 제외한 후 등수를 정렬하고, 완호의 등수를 구하는 아이디어다.

문제점

인센티브 제외하느라 배열을 한 번 순회하고, 등수를 정렬하느라 배열을 또 한번 순회하고, 완호의 등수를 구하느라 다시 한 번 배열을 순회하게 된다. 따라서 총 3번 배열을 순회하기 때문에 배열이 길어지게되면 시간 초과 문제가 발생하게 된다.

그렇다면 어떻게 해결할 수 있을까?

아이디어 2 : 인센티브 제외 -> 완호 등수 구하기

완호의 등수를 계산할 때 완호의 등수자체가 중요한 것이지 위의 등수가 어떻게 구성되어있는지가 중요한 것은 아니다. 즉, 1등, 2등이 누구고 완호는 몇등이지가 아니라 단순히 완호의 등수만 구하면 되기 때문에 정렬을 할 필요가 없어진다.

 

그렇게 정렬을 제외하고 코드를 작성했다.

문제점

여전히 시간 초과 문제가 발생했다.

 

왜 그런 것일까.

경우의 수를 생각해보자.

 

기본적으로 인사고과 합이 낮은 경우 다른 사원에 비해 두 점수가 모두 낮을 확률이 높아진다. 그런데 우리는 이미 순회를 돌기 전 완호의 인사고과 두 점수를 비교하고 있다.

따라서 순회를 돌 때에는 완호의 등수가 꽤나 높을 가능성이 높다. 따라서 인센티브에서 제외될 인원은 완호의 윗 등수보다 아랫등수에 많이 분포할 가능성이 높다.

그렇기 때문에 완호의 등수를 먼저 구한 다음 인센티브를 제외하는 것이 배열 순회 횟수를 줄일 수 있는 방법이라고 생각한다.

아이디어 3 : 완호의 윗 등수 구하기 -> 인센티브 제외하기

위에서 추론한 문제점을 토대로 윗 등수인 사원들만 구한 다음 그 안에서 인센티브를 제외하는 알고리즘을 구현했다.

최종 코드

function solution(scores) {
    const [first, second] = scores[0];
    if (scores.length === 1) return 1;
    
    if (scores.some((re) => re[0] > first && re[1] > second)) return -1

    let reserve = scores.filter((score) => score[0] + score[1] > first + second)
    reserve = reserve.filter((score) => !reserve.some((re) => re[0] > score[0] && re[1] > score[1]))

    return reserve.length+1
}

 

그 결과 통과!!

역시 순서의 문제가 맞았던 것 같다.