문제 설명
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.
제한 사항
works는 길이 1 이상, 20,000 이하인 배열입니다.
works의 원소는 50000 이하인 자연수입니다.
n은 1,000,000 이하인 자연수입니다.
내가 작성한 코드
function solution(n, works) {
while(n!=0){
works.sort((a,b)=> b-a)[0] -= 1
n--
}
if(works[0] < 0) return 0
console.log(works)
let sum = works.reduce((acc, cur)=>{
console.log(acc, cur)
return acc += cur**2
})
return sum
}
위와 같이 작성 했으나 테스트1에서 계속 10을 반환한다.
중간에 정상적으로 제곱이 되어 들어가는 출력을 확인했는데 계속 10을 반환한다.
천천히 출력을 살펴보니 처음에 2가 출력되는게 이상했다. 제곱된 수가 들어가야하는데 2가 계속 출력된다.
생각을 해보니 처음값은 그대로 들어간다는 뜻인것 같다.
즉, Reduce함수를 사용할 때에는 처음 값은 원하는 처리가 되지 않고 들어간다는 것이다.
function solution(n, works) {
while(n!=0){
works.sort((a,b)=> b-a)[0] -= 1
n--
}
if(works[0] < 0) return 0
works[0] **=2 // 초기값 세팅
let sum = works.reduce((acc, cur)=>{
return acc += cur**2
})
return sum
}
위와 같이 초기값을 세팅해서 해결했다.
실행결과 테스트 문제들은 전부 통과했으나 효율성에서 실패했다.
로직적으로는 알맞게 구현했으나 빅오복잡도 즉, 시간복잡도에서 실패한 셈이다.
내용을 파악해보니 n제곱인 경우가 너무 많아서다. 이럴 땐 이진힙 자료구조를 이용해야 하는것 같다.
이 내용은 아직 학습이 필요하기 때문에 일단은 여기서 마무리 짓고 자료구조 공부를 한 뒤에 다시 풀어보기로 했다.
역시 레벨3은 쉽지 않다.....
