야근 지수 [자바]

 

🧫 문제 분석

✔️ 출처

야근 지수 level 3

📖 문제

 

약간 탐욕법 문제인듯하다.

Demi가 퇴근까지 N시간 남았고, 그 시간안에 남은 작업량(works)를 적절히 분배해서 작업을 하여 

야근 피로도가 최소가되게 즉, S={w^2 ∣ w∈works} 이 최솟값이 되게 하면 된다. 

 

 

예시 1번을 보면 

4,3,3 이 남은 작업량, n이 퇴근까지 4시간 남았다.

야근 피로도는 제곱이기에 값이 매우 커진다. 따라서 남은 작업량들을 균등하게 만들어야한다. 

 

works[0] - 2, works[1] - 1,  works[2] - 1

= 2, 2, 2

이렇게 분배하여 최솟값을 구하면 된다.

 

 

 

풀이 정리

해당 문제는 배열로 풀면 좋을 것 같아서 배열로 풀어보았다.

각 works의 값을 인덱스로 하고 개수를 카운팅한 뒤 

max값에서 n이 0이 될때까지 개수를 빼주어 

works를 균등하게 한다. 

 

예를 들어 예시 1번의 경우

arr[0] arr[1] arr[2] arr[3] arr[4] 
  0      0      0      2     1

 

이렇게 카운팅하고

 

최댓값 4를 n과 비교하여 개수가 더 적다면 n - arr[4] 를 한 후 arr[4]의 개수를 arr[3]에 더한다. 

arr[4]는 당연히 뺐으므로 0으로 초기화해준다. 

 

이런식으로 균등히 빼주면 된다. 

 

 

자세한 것은 코드를 참조하길 바란다. 

 

---

🔅 문제 풀이

import java.util.Arrays;

class Solution {
    // 야근 피로도 = 남은일 ^ 2
    // 그리드 
    // 1시간동안 작업량 1만큼 처리
    
    public long solution(int n, int[] works) {
        long[] schedule = new long[50001];
        long answer = 0;
        int max = 0;
        
        for (int i = 0; i < works.length; i++) {
            max = Math.max(max, works[i]);
            schedule[works[i]]++;
        }
        
        // max 에서 하나씩 내림
        while (max > 0 && n > 0) {
            
            // max의 개수를 n 과 비교하여 더 작다면 n에서 빼고 max-1로 옮김
            if (schedule[max] <= n) {
                n -= schedule[max];
                schedule[max-1] += schedule[max];
                schedule[max--] = 0;
                // max의 개수가 n보다 크다면 
            } else {
                schedule[max] -= n; // 기존 max에서 n을 빼고
                schedule[max-1] += n; // -1된 max에 n을 추가
                break; // max의 개수가 n보다 크므로 n은 더이상 없음
            }
        }
        
        // 야근 피로도 계산
        for (int i = max; i >= 1; i--) {
            if (schedule[max] > 0) {
                answer += i * i * schedule[i]; // 현재 남은 작업량 ^2 * 개수
            }
        }
        
        return answer;
        
        
    }
}

 

❗ 오답노트 / 필요한 지식