인사고과 [Lv. 3] (C++)

프로그래머스

완호네 회사는 인사고과에 따라 인센티브를 지급합니다.

각 사원마다 근무 태도 점수와 동료 평가 점수가 있는데 다른 임의의 사원보다 두 점수가 모두 낮다면

인센티브를 받지 못합니다. 인센티브를 받는 사원들 중에 완호가 몇등인지 찾아주세요.

(두 점수의 합으로 등수를 정합니다)

 

풀이 방법

이 문제를 풀면서 난관에 부딪히는 부분은 인센티브를 받을 수 있는 사원인지 아닌지 체크하는 부분입니다.

이때 모든 사원을 순회하여 문제를 풀면 시간 초과가 될 수 밖에 없습니다.

그래서 우리는 최대 nlogn의 속도로 문제를 풀어야합니다.

 

인센티브를 받을 수 없는 상황은 나보다 두 점수가 모두 높은 사원이 있는 상황입니다.

여기서는 근무 태도 점수를 A, 동료 평가 점수를 B라고 하겠습니다.

입력받은 scores 배열을 A를 기준으로 오름차순 정렬후

이진 탐색 알고리즘을 이용하면 나의 A보다 바로 위의 점수를 찾을 수 있습니다.

 

이렇게 찾은 A부터 scores배열 끝까지 나의 B보다 큰 B가 있다면 인센티브를 받을 수 없는 것 입니다.

(오름차순 정렬했으니 A는 무조건 나보다 큼)

여기서 핵심은 A부터 scores배열 끝까지입니다. dynamic programming을 생각해볼 수 있겠죠

 

scores 배열을 오름차순 정렬할때 A가 서로 같다면 B를 기준으로 내림차순 정렬합니다.

예시 -- [1, 4], [2, 1], [3, 3], [3, 2], [3, 1]

 

배열의 뒤에서 부터 가장 큰 값을 따로 저장합니다.

dp[6] = {4, 3, 3, 2, 1}

 

나보다 큰 A를 이진 탐색 알고리즘으로 찾은 후에

해당 index를 dp 배열에서 확인해보면 나보다 큰 B가 있는지 없는지 빠르게 찾을 수 있게 됩니다.

 

정답 코드

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

using namespace std;

int solution(vector<vector<int>> scores) {
    int a = scores[0][0];
    int b = scores[0][1];
    scores[0] = {-100, -100}; // 나와 비교하는건 없앰
    
    // A를 기준으로 오름차순, 같다면 B를 기준으로 내림 차순
    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];
    });


	// (i ~ 끝까지) 가장 큰 값을 저장
    vector<int> dp(scores.size());
    dp[dp.size()-1] = scores.back()[1];
    for (int i = dp.size()-2; i >= 0; i--)
        dp[i] = max(scores[i][1], dp[i+1]);
   
    
    // 1등부터 시작
    int answer = 1;
    for (int i = 1; i < scores.size(); i++)
    {
        auto& score = scores[i];
        // 내가 인센티브를 받을 수 없으면 -1 반환
        if (score[0] > a && score[1] > b)
            return -1;
        
        // 현재 위치부터 배열의 끝까지 이진탐색
        int min = i;
        int max = scores.size() - 1;
        while (min < max)
        {
            int mid = (min + max) / 2;
            if (scores[mid][0] > score[0])
            {
                max = mid - 1;
            }
            else
                min = mid + 1;
        }
        
        if(min < dp.size() && dp[min] > score[1])
            continue;
        
        // 내가 이기면 등수 ++
        if (score[0] + score[1] > a + b)
            answer++;
    }
   
    return answer;
}