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

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

접근

여러 사원의 석차 중에서 완호의 석차만 생각하면 되므로 인센티브를 못 받는 사원을 먼저 정하고 그 중 완호 보다 높은 점수의 사원들을 계수하면 문제를 해결할 수 있다.

하지만 인센티브를 못 받는 사원을 정할 때 단순하게 이중 for문으로 순차 탐색을 할 수 없다. scores 의 길이 제한이 $1\leq{...}\leq{100,000}$ 이기 때문이다.

이를 위해 $O(N\log{N})$ 의 시간 복잡도를 가지는 정렬을 이용한다.

먼저 근무 태도 점수를 기준으로 내림차순 정렬 후 같은 근무 태도 점수에 대해 동료 평가 점수를 기준으로 오름차순 정렬하면 iteration할 때 근무 태도 점수에 대응하는 최대 동료 평가 점수를 저장하여, 이보다 작으면 인센티브를 받지 못하는 사원으로 간주한다.

소스코드(Java)

import java.util.*;

class Solution {

    public int solution(int[][] scores) {
        int[] target = scores[0];

        Arrays.sort(scores, (arr1, arr2) -> {
            if(arr1[0] == arr2[0]) {
                return arr1[1] - arr2[1];
            }
            return arr2[0] - arr1[0];
        });

        int max = scores[0][1];

        for(int i = 1; i < scores.length; i++) {
            if(scores[i][1] < max) {
                if(scores[i][0] == target[0] && scores[i][1] == target[1]) {
                    return -1;
                }
                scores[i][0] = -1;
                scores[i][1] = -1;
            } else {
                max = scores[i][1];
            }
        }

        Arrays.sort(scores, (arr1, arr2) -> {
            return (arr2[0]+arr2[1]) - (arr1[0]+arr1[1]);
        });

        int rank = 1;

        for(int i = 0; i < scores.length; i++) {
            if(target[0]+target[1] < scores[i][0]+scores[i][1]) {
                rank += 1;
            } else {
                break;
            }
        }

        return rank;
    }
}