C++ 프로그래머스 코딩테스트 - 야근 지수 (12927)

야근 지수

Level 3

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

프로그래머스

 

 

퇴근까지 남은 시간 N이 주어지고, 작업량 리스트가 주어진다.

야근 지수의 최솟값을 리턴해야 하는데, 야근 지수를 가장 작은 수로 만들려면,

 

작업량 리스트의 숫자들의 차이가 적게 나야한다.

예를들어 [10, 9, 8, 1] 의 작업량 리스트와 시간 5 값이 주어질 때, 

[8, 8, 6, 1] 보다 [7, 7, 8, 1] 가 야근 지수가 더 낮다. (리스트의 숫자들의 격차가 최대한 적도록)

 

 

풀이를 그림으로 표현하면,

값이 높은 순서대로 정렬한 다음 첫 번째부터 검사하면서, 다음 값이 현재 값 보다 작으면, 그 차이만큼 값들을 빼준다.

 

 

 

 

효율성 테스트 통과를 위해 다음 값이 작아졌을때, 작업량 값의 차이 값을 구하고 - diff

남은 시간 N을 계산하여 값을 빼주었다.

 

 

 

 

나의 풀이

long long solution(int n, vector<int> works)
{
    auto result = [&works]()->long long {
        long long sum = 0;
        for (int i : works)
            sum += pow(i, 2);
        return sum;
    };
 
    std::sort(works.begin(), works.end(), greater<long long>());
 
    long long idx = 0;
    while (n > 0)
    {
        // 마지막까지 다 돌았을 때
        if (idx + 1 == works.size())
        {
            long long diff = n / (idx + 1);
            if (diff == 0) diff = 1; // 나눗셈으로 손실된 값 보정
 
            if (works[0] - diff < 0) return 0;
 
            // 처음 ~ 현재 값까지 모두 빼준다.
            for (long long i = 0; i < idx + 1; ++i)
            {
                works[i] -= diff;
                n -= diff;
                if (n <= 0)
                    return result();
            }
            continue;
        }
        // 현재 작업량보다 작아진 값을 찾는다.
        else if (works[idx] != works[idx + 1])
        {
            // 다음 작업량 과의 차이 get.
            long long diff = works[idx] - works[idx + 1];
 
            // n 이 처음 ~ 현재 작업량을 모두 빼주기 충분하지 않다면,
            if (diff * (idx + 1) > n)
                diff = n / (idx + 1);
 
            if (diff == 0) diff = 1; // 나눗셈으로 손실된 값 보정
 
            // 처음 ~ 현재 값까지 모두 빼준다.
            for (long long i = 0; i < idx + 1; ++i)
            {
                works[i] -= diff;
                n -= diff;
                if (n <= 0)
                    return result();
            }
        }
        ++idx;
    }
    return result();
}