문제

Programmers Lv3, 인사고과

핵심

• 입력의 크기가 100,000이라 대략 $O(N * logN)$ 이하 알고리즘을 사용한다.
• 인사고과에 따라 인센티브를 지급하는데, 근무 태도 점수와 동료 평가 점수가 어떤 임의의 사원보다 두 점수 모두 낮은 경우 인센티브를 받지 못한다. 인센티브는 석차에 따라 지급하기에 총점수에 따라 완호의 석차를 구해야 한다.
• 크게 아래 두 가지 사항을 판단해야 한다. 첫째로, 완호가 인센티브를 받을 수 있는지다. 둘째로 받을 수 있다면 순위를 구해야 한다.
• 처음 접근할 때 놓친 부분은 완호보다 총점이 높은 사람들은 당연히 인센티브를 받을 수 있다고 생각하여 등수를 계산했다. 하지만 아래와 같이 완호보다 총점이 높지만, 인센티브를 받을 수 없어 등수에 포함되지 않는 사원이 존재한다. 총점과 인덱스를 저장해놓고 정렬하여 풀었는데, 이 경우 특정 케이스를 맞출 수 없다. 아래와 같이 반례가 존재하기 때문이다.

{2, 0} - 완호
{2, 7} - 1등
{1, 6} - 2등이 아니라 인센티브 제외 대상이다.

그럼 어떻게 인센티브를 받을 수 있는지와 등수를 계산할 때 어떻게 $O(N^2)$미만의 알고리즘을 사용할 수 있을까?

• 첫 번째 원소를 내림차순으로, 두 번째 원소를 오름차순으로 정렬한 다음 완호가 인센티브 제외 대상인지, 제외 대상이 아니라면 몇 등인지 하나의 반복문을 돌면서 찾아낼 수 있다.

    for (auto& e : scores) {
    	if (target[0] < e[0] && target[1] < e[1]) {
        	return -1;
    	}
        
        if (cmax <= e[1]) {
        	if (target_sum < e[0] + e[1]) {
            	ans++;
        	}
        	cmax = e[1];
    	}
    }

• 모든 사원의 점수를 순회하며 완호가 인센티브 제외 대상이라면 -1을 리턴한다. 두 번째 if문은 완호의 등수를 계산하기 위함인데, e[0]은 이미 내림차순으로 정렬되어 있고, e[1]이 더 커졌을 경우에만 완호보다 등수가 높은 사람이 존재할 가능성이 있다는 것이다. e1이 더 커졌을 때 완호 점수보다 해당 사원의 점수가 높다면 완호의 등수를 밀어낸다.
• 헷갈릴 수 있는 점은 왜 2번째 원소를 내림차순으로 정렬하는지다. 한 번의 탐색으로 완호보다 높은 점수를 가진 사람을 판별하기 위해서 필요하다. 낮은 점수부터 확인해야 누락하지 않고 구할 수 있다. 예시로 [[0, 4], [5, 4], [5, 3], [5, 2]] 이러한 데이터가 있을 때 사원을 두 번째 원소로 정렬하지 않으면 원호의 등수는 4등이 아닌 2등이 된다. [5, 4]에서 최댓값인 4로 갱신했기 때문에 그다음부터는 원호보다 큰 점수들이어도 누락된다.

개선

코드

C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> scores) {
    
    vector<int> target = scores[0];
	int target_sum = target[0] + target[1];
    
	sort(scores.begin(), scores.end(), [](auto& a, auto& b) {
		if (a[0] != b[0]) 
			return a[0] > b[0];
		return a[1] < b[1];
	});

    int ans = 1;
    int cmax = 0;

    for (auto& e : scores) {
    	if (target[0] < e[0] && target[1] < e[1]) {
        	return -1;
    	}
        
        if (cmax <= e[1]) {
        	if (target_sum < e[0] + e[1]) {
            	ans++;
        	}
        	cmax = e[1];
    	}
    }

    return ans;
}

Java

import java.util.*;

class Solution {
    public int solution(int[][] scores) {
        
        int[] target = scores[0];
        int target_sum = target[0] + target[1];
        
        Arrays.sort(scores, (a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(b[0], a[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int ans = 1;
        int cmax = 0;

        for (int[] e : scores) {
            if (target[0] < e[0] && target[1] < e[1]) {
                return -1;
            }

            if (cmax <= e[1]) {
                if (target_sum < e[0] + e[1]) {
                    ans++;
                }
                cmax = e[1];
            }
        }

        return ans;
    }
}