[프로그래머스] 야근 지수 (level3, JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=java

프로그래머스

---

※ 문제설명

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

 

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력 예

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

 

입출력 예 설명

입출력 예 #1
n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]입니다. 이 때 야근 지수는 22 + 22 + 22 = 12 입니다.

---

※ JAVA 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        long sumWorks = Arrays.stream(works).sum();
        if(sumWorks <= n) {
            return answer;
        }
        
        // boxing
        Integer arr[] = Arrays.stream(works).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder());

        while(n > 0) {
            Arrays.sort(arr, Collections.reverseOrder());
            int maxValue = arr[0]; // 가장큰 값

            // 가장큰 상단부분과 같은 숫자들을 순차적으로 자른다
            for(int i = 0; i < arr.length && arr[i] >= maxValue; i++) {
                if(n == 0) break;
                else {
                    arr[i]--;
                    n--;
                }
            }
        }

        // unboxing
        int unArr [] = Arrays.stream(arr).mapToInt(Integer::intValue).toArray();
        answer = SumVal(unArr);
        return answer;
    }
    
    public static long SumVal(int[] arr) {
        long result = 0;

        for(int i = 0; i < arr.length; i++) {
            result += Math.pow(arr[i], 2);
        }

        return result;
    }
}

---

※ 문제설명

필요한 과정은 남은 works 배열의 제곱합의 최소값을 구해야한다. 그렇다면 어떻게 해야 제곱값들의 합이 최소가 나올 수 있을까? 

이를 알기위해 몇가시 테스트를 진행했다.

 

1) 하나의 숫자만 높고 나머지 금액들이 작다

4, 1, 1, 1 = 18

2) 각각의 금액들을 일정하게 깎아내려간다.

2, 2, 2, 2 = 16

 

결론적으로 몇번의 테스트를 통해 전체 높이의 평균높이가 낮은경우 제곱합이 가장작은 수를 만들 수 있다는 결론을 얻을 수 있었다.

 

1. works를 내림차순 정렬하였다.

2. 가장큰 work를 찾는다.

3. work와 같은 숫자를 1씩 뺀다. 이때 가장큰 work보다 작은 숫자가 나오면 다시 처음으로 돌아간다.

4. 1씩 빼면서 n을 1씩 감소시키고 n이 0이 되면 종료한다.

 

감사합니다.