코딩 테스트 - 인사고과

인사고과

문제 링크 : 인사고과

문제 설명

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

입출력 예

scores	result
[[2,2],[1,4],[3,2],[3,2],[2,1]]	4

풀이 방법

• 어떤 사원이 다른 임의의 사원보다 두 점수 모두가 낮은 경우에는 인센티브에서 제외가 된다. 이를 먼저 확인하기 위해서 처음에는 두 점수의 합을 통해서 정렬한 다음에 비교해보고자 했다. 두 점수의 합이 크거나 같다면 무조건 하나의 점수는 크기 때문에 비교를 안 해도 되니까 더 효율적이라고 생각했는데, 똑같이 O(N^2)의 시간복잡도가 걸리는 것은 마찬가지였다. 해당 문제는 N이 100,000이기 때문에 최대 O(NlogN)의 시간복잡도만 허용하기 때문에 해당 방법은 옳지 않다고 생각했다.
• 그럼 하나의 점수를 통해서 먼저 정렬을 하고, 다른 점수 하나를 이용해서 이를 해결하고자 했다. 근무 태도 점수 기반으로 먼저 내림차순 정렬을 하고, 가장 높은 동료 평가 점수를 저장해놓고, 그것보다 작으면 인센티브에서 제외된다고 생각했다. 따라서 정렬할 때, 근무 태도 점수가 같으면 동료 평가 점수는 오름차순으로 정렬을 해서 같은 경우의 예외를 처리했다.
• 위의 방법으로 인센티브를 받을 수 없는 경우를 제외하고, 점수 합을 저장해놓고 이를 기반으로 완호의 점수합과 비교해서 순위를 찾았다.
  -> 해당 알고리즘은 기본 순회하는데 O(N)의 시간복잡도가 걸리고, 정렬하는데 O(NlogN)의 시간복잡도가 걸리기 때문에 최대 O(NlogN)의 시간복잡도로 알맞은 풀이방법이라고 생각한다.

구현

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

using namespace std;

int solution(vector<vector<int>> scores) {
    vector<int> wanho = scores[0];
    
    // 근무 태도 점수 기반으로 내림차순 정렬, 같은 경우 동료 평가 점수 기반으로 오름차순 정렬
    sort(scores.begin(), scores.end(), [](vector<int>& a, vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    });
    
    // 근무 태도 점수도 낮고, 동료 평가 점수도 낮은 경우 제외하기
    int maxScore = 0;
    vector<int> sums;
    
    for(vector<int>& v : scores){
        if(v[1] < maxScore) {
            if(v == wanho) return -1;
        } else{
            sums.push_back(v[0] + v[1]);
            maxScore = max(maxScore, v[1]);
        }
    }
    
    // 점수 합을 기반으로 순위 측정하기
    int answer = 1;
    int wanhoSum = wanho[0] + wanho[1];
    sort(sums.rbegin(), sums.rend());
    
    for(int i = 0; i < sums.size(); i++){
        if(sums[i] == wanhoSum){
            break;
        }
        answer++;
    }
    
    return answer;
}