[프로그래머스] [Level 3] 인사고과 (C++)

문제 설명

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

풀이

생각보다 어려웠던 문제다…

이 문제에서 핵심은 인센티브를 받지 못하는 사원을 걸러내는 부분이라고 생각하는데, 만약 아무 생각 없이 이중 반복문을 사용한다면, 시간 복잡도는 이 되서 시간 초과가 난다.

이를 위해 우선 scores 배열을 A 점수에 대해서 내림차순으로 정렬하고, 만약 A 점수가 같다면 B 점수에 대해 오름차순으로 정렬한다.

여기서 B 점수에 대해 오름차순으로 정렬하는 이유는 아래 코드를 보면 이해가 가겠지만, maxB 값이 업데이트되어 인센티브를 받지 못하는 경우가 생길 수 있기 때문이다.

또한, 완호가 1 번째 사원이므로 a + b가 targetScore보다 큰 경우에만 answer을 1 증가시킨다.


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

using namespace std;

bool compare(vector<int> a, vector<int> b) {
    if(a[0] > b[0]) {
        return true;
    } else if(a[0] == b[0]) {
        return a[1] < b[1];
    } else {
        return false;
    }
}

int solution(vector<vector<int>> scores) {
    int answer = 1;
    int targetA = scores[0][0];
    int targetB = scores[0][1];
    int targetScore = targetA + targetB;
    int maxB = -1;
    
    sort(scores.begin(), scores.end(), compare);
    
    for(int i = 0; i < scores.size(); i++) {
        int a = scores[i][0];
        int b = scores[i][1];
        
        if(b >= maxB) {
            maxB = b;
            
            if(a + b > targetScore) {
                answer++;
            }
        } el1se if(b < maxB) {
            if(a == targetA && b == targetB) { // 만약 그게 완호인 경우
                answer = -1;
                break;
            }
        }
    }
    
    return answer;
}