1. 문제
문제 설명
회사원 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입니다.
입출력 예 #3
남은 작업량이 없으므로 피로도는 0입니다.
2. 풀이
효율성을 고려하지 않으면 쉽게 풀 수 있는 문제다.
간단하게 풀 수 있어서 처음에는 쉽다고 생각했지만 효율성에서 시간초과가 발생했다.
while 문을 사용하여 계속해서 오름차순으로 정렬을 하고, 이렇게 하면 최댓값이 항상 맨 앞에 위치하게 된다. 최댓값이 0이라면 탈출을 하고 아니라면 최댓값을 계속해서 -1 해주고, n도 -1 해준다. 계속해서 정렬을 해야한다는 점이 시간초과를 발생시켰다.
// 처음 작성한 코드(효율성 통과X)
function solution(n, works) {
while (n !== 0) {
works.sort((a, b) => b - a);
if (works[0] === 0) return 0;
--works[0];
--n;
}
return works.reduce((acc, cur) => acc + cur ** 2, 0);
}위의 코드와 별로 달라진 점이 없다. 달라진 것은 while문을 안에 모든 값의 합이 0이라면 탈출을 한다는 것, 그리고 indexOf를 사용하여 최댓값을 찾아 해당 값을 -1 해준다는 것이다.
이것도 마찬가지로 시간초과가 발생하여 통과하지 못했다.
// 두 번째로 작성한 코드(효율성 통과X)
function solution(n, works) {
while (n !== 0) {
if (works.reduce((a, c) => a + c, 0) === 0) return 0;
works[works.indexOf(Math.max(...works))] -= 1;
--n;
}
return works.reduce((acc, cur) => acc + cur ** 2, 0);
}그래서 고심하다가 한 블로그를 발견했는데 풀이가 너무 깔끔해서 참고하여 코드를 작성했다.
아래 코드에서 고려한 점을 정리하면 다음과 같다.
- 남은 작업량의 합이 퇴근까지 남은 시간(
n)보다 작거나 같으면 피로도가 없으므로if문으로 초반에 걸러준다. - 각 일에 대한 작업량(
works)를 오름차순으로 정렬하여sorted변수에 저장한다. 이렇게 하면sorted의 맨 앞에 있는 값이works의 최댓값이 된다. n이 유효할 동안while문을 돌린다.sorted[0]값을max_num으로 저장한다.for문을sorted의 길이만큼 반복하면서sorted[i]값이max_num이상이라면sorted[i]값을 -1 해준다. 이렇게 하면 해당 배열을 계속해서 정렬할 필요없이max_num은 항상 최댓값이 된다.for문을 돌릴 동안n이 0이 되면while문을 탈출한다.
function solution(n, works) {
// 남은 총 작업량보다 퇴근까지 남은 시간이 같거나 크다면
// 모든 일을 처리할 수 있으므로 피로도가 없다
if (works.reduce((a, c) => a + c, 0) <= n) return 0;
let sorted = works.sort((a, b) => b - a);
// 퇴근까지 남은 시간이 유효할 동안
while (n) {
// 최댓값은 sorted의 맨 앞에 고정
let max_num = sorted[0];
for (let i = 0; i < sorted.length; i++) {
// sorted의 값 중 최댓값 이상인 값이 있다면 -1 하기
// 따라서 최댓값은 항상 맨 앞에 위치함(재정렬할 필요X)
if (sorted[i] >= max_num) {
sorted[i] -= 1;
n -= 1;
}
// 퇴근까지 남은 시간이 다 소진되면 탈출
if (!n) break;
}
}
return works.reduce((acc, cur) => acc + cur ** 2, 0);
}이렇게 작성하면 효율성도 통과할 수 있다.
3. 참고한 풀이
