https://programmers.co.kr/learn/courses/30/lessons/12927
야근 지수
문제 설명
회사원 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 입니다.
입출력 예 #2
n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 12 + 12 + 22 = 6입니다.
문제 풀이
첫 문제 풀이
function solution(n, works) {
var answer = 0;
works = works.sort((a,b) => b-a);
let total = works.reduce((a,c) => a+c)
while(n>0 && total !== 0) {
if(works[0] < works[1]) {
works = works.sort((a,b) => b-a);
}
works[0] = works[0] - 1
n --;
total --;
}
works.forEach(el => answer += el*el)
return answer;
}야근 지수는 남은 일의 제곱을 더하기 때문에 남은일의 숫자가 최대한 동등하게 떨어지는 것이 야근지수가 떨어지는 일이라고 생각했고 문제를 해결하기 위해서
- 가장 큰 수에서 1 씩 빼기
- 가장 큰 수보다 그 다음으로 큰 숫자가 커질 경우 다음 숫자를 가장 큰 숫자로 만들어서 1 빼주기
- 남은시간이 0이 되거나 모든 일이 끝날 경우 반복문 멈추고 남은 숫자 제곱해서 더해주기.
이 순서로 문제를 해결해야겠다고 생각했다.
그래서 먼저 일의 순서를 일이 가장 많은 것부터로 정렬해 준 뒤
전체 일의 양을 구하고 남은시간이 0보다 클 경우와 일의 총량이 0이 아닐경우 계속 반복되는 반복문을 돌려서
가장 큰 숫자가 두번째 숫자보다 작을 경우 정렬을 다시 해주고
가장 큰 숫자와 남은시간, 일의 총양을 1 빼준다.
그리고 반복문을 반복하면 문제가 해결될것이라 생각했고 실제로 효율성 테스트를 제외하고는 모두 통과를 했다.
하지만 효율성 테스트에서 문제가 생겼고 문제의 원인이 sort를 계속 해줘야 하기 때문에 시간이 오래걸린다고 생각했고 이 문제를 해결하기 위해서 sort가 아닌 다른 방법을 사용해야한다고 생각했다.
function solution(n, works) {
var answer = 0;
works = works.sort((a,b) => b-a);
let total = works.reduce((a,c) => a+c)
while(n>0 && total !== 0) {
for (let i = 1; i<works.length; i++) {
if(works[0] < works[i]) {
let m = works[0];
works[0] = works[i]
works[i] = m;
break;
}
}
works[0] = works[0] - 1
n --;
total --;
}
works.forEach(el => answer += el*el)
return answer;
}sort말고 다른 방법으로 해결하기 위해서 반복문을 사용해서 가장 큰수works[0] 을 바꿔주는 방법을 사용했다.
반복문을 돌리면서 가장 큰 수works[0]이 1씩 줄어들게 되고 그러면 works[1] 보다 1이 더 낮아지는 상황이 오는데 그렇게 되면 works[1]이 works[0]과 자리를 바꾸게 되고 works[0]이 1 줄어들게 되면서 works[0] 과 works[1] 이 같은 숫자가 된다.
그렇게 되면서 2번째 인덱스부터 비교를 하게되고 큰 숫자가 없는 경우 works[0]이 다시 1이 줄게 된다.
이 방법으로 남은 시간이 0이 될 때 까지 진행한 뒤 남은 숫자를 제곱해서 더해주게 되면 정답이 나온다.
