링크
https://school.programmers.co.kr/learn/courses/30/lessons/12927
문제
회사원 Demi는 가끔은 야근을 하는데, 야근을 하면 야근 피로도가 쌓인다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값이다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 Demi건데, 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성하라.
예제로 이해
works : [4, 3, 3]
n : 4
result : 12
피로도를 최소로 한다는 것은 works의 각 요소의 제곱의 합을 최소로 만들겠다는 것과 같다.
제곱의 합을 최소로 만드는 방법은 각 숫자들을 최대한 같은 수에 가깝게 유지하면 된다.
예를 들어 위의 works에서 4시간 동안 4짜리 작업을 완료한다면 [0, 3, 3]이 되어 총 피로도는 18이 된다.
하지만 각 숫자들을 최대한 같은 수에 가깝게 하면 각 요소들은 [2, 2, 2]가 될 것이며 총 피로도는 12가 될 것이다.
이렇듯이 works 내의 가장 큰 수에 대해서 -1을 n 만큼 반복하면 원하는 결과를 얻어 낼 수 있다.
코드
class MaxHeap {
constructor() {
this.value = []
}
swap(index1, index2) {
let temp = this.value[index1]
this.value[index1] = this.value[index2]
this.value[index2] = temp
}
parentIndex(index) {
return Math.floor((index - 1) / 2)
}
leftChildIndex(index) {
return index * 2 + 1
}
rightChildIndex(index) {
return index * 2 + 2
}
parentValue(index) {
return this.value[this.parentIndex(index)]
}
leftChildValue(index) {
return this.value[this.leftChildIndex(index)]
}
rightChildValue(index) {
return this.value[this.rightChildIndex(index)]
}
add(value) {
this.value.push(value)
let index = this.value.length - 1
while(true) {
if(this.value[index] > this.parentValue(index)) {
let parentIndex = this.parentIndex(index)
this.swap(index, parentIndex)
index = parentIndex
} else {
break
}
}
}
minus() {
let index = 0
this.value[0] -= 1
while(true) {
let childIndex = 0
if(this.value[index] < this.leftChildValue(index)) {
childIndex = this.leftChildIndex(index)
this.swap(index, childIndex)
index = childIndex
} else if(this.value[index] < this.rightChildValue(index)) {
childIndex = this.rightChildIndex(index)
this.swap(index, childIndex)
index = childIndex
} else {
break
}
}
}
result() {
if(Math.max(...this.value) <= 0) {
return 0
} else {
return this.value.reduce((acc, cur) => {
return acc + cur * cur
}, 0)
}
}
}
function solution(n, works) {
let heap = new MaxHeap()
works.map(el => {
heap.add(el)
})
for(let i = 0; i < n; i++) {
heap.minus()
}
return heap.result()
}코드 풀이
이 문제는 최대힙을 사용하지 않고 풀이를 진행하면 문제의 테스트 케이스들은 통과를 할 수 있지만, 효율성 부분에서 모두 시간 초과를 겪는다.
다음은 효율성을 고려하지 않은 코드이다.
function solution(n, works) {
for(let i = 0; i < n; i++) {
if(Math.max(...works) === 0) break
works[works.indexOf(Math.max(...works))] -= 1
}
return works.reduce((acc, cur) => {
return acc + cur * cur
}, 0)
}works에서 가장 큰 수에서 -1을 n 만큼 반복 진행한다는 개념에서는 올바른 코드이지만, 효율적인 면에서 works의 크기가 매우 크거나, n의 값이 매우 크면 실행 시간이 매우 오래 걸릴 가능성이 있다.
따라서 해당 문제를 배열 전체를 탐색하는 방식이 아닌 탐색에 걸리는 시간을 줄이는 방식으로 코드가 작성이 되어야한다.
이 문제는 최대힙을 사용해서 탐색 시간을 O(n) = log2(n)으로 줄일 필요가 있다.
js에서는 외부 라이브러리가 아닌 이상 힙을 기본적으로 제공하지 않기 때문에 힙의 개념을 가진 class 객체를 새로 선언한다.
힙 자체는 배열을 가지고 자식노드의 인덱스, 자식노드의 값, 부모노드의 인덱스, 부모노드의 값, 부모노드와 자식노드의 값을 변경, 새로운 노드 넣기 등의 과정이 필요하다.
따라서 해당 작업을 진행할 수 있는 함수들을 모두 힙 내부에 선언해준다.
위의 과정에 더해서 이 문제는 배열 내 요소들의 최대값에 -1씩 해주는 과정이 필요하므로 해당 작업의 코드도 함수로 만들어주고 전체 요소의 제곱의 합을 반환하는 함수도 함께 작성한다.
힙
이 문제는 힙을 이해해야 해결이 가능한 문제이다.
힙은 배열을 이용해서 값을 저장하고, 찾는다는 점에서는 같지만, 탐색의 과정이 일반 배열에서 찾는 것과는 다른 모습을 띈다.
힙은 탐색 및 값의 저장에 최적화된 탐색 개념으로 한번 탐색할 때마다 찾으려는 범위가 절반씩 줄어들기 때문에 시간복잡도 면에서 최적의 모습을 보인다.
힙은 부모노드와 자식노드 두 개가 반복된다고 생각하면 된다. 하나의 부모노드는 2개의 자식노드를 가지며, 각각의 자식노드는 그 자신이 부모노드가 될 수 있다. 따라서 하나를 탐색해 들어가는 과정의 시간복잡도는 O(n) = log2(n)이 될 수 있는 것이다.
힙은 최대힙 혹은 최소힙 두가지로 구분되는데 쉽게 말해 부모노드의 값이 자식노드의 값보다 크면 최대힙, 작으면 최소힙이라고 부른다.
각각의 노드는 자식노드 2개를 가지는데 각 자식노드의 인덱스는 아래의 식을 만족한다.
왼쪽 자식노드의 index = 부모의 index 2 + 1
오른쪽 자식노드의 index = 부모의 index 2 + 2
반대로 부모의 인덱스는 자식노드의 인덱스 값에 대해 다음의 식을 만족한다.
부모의 index = Math.floor((자식노드의 index - 1) / 2)
인덱스 값을 알면 값을 알아오는 것은 배열처럼 접근하여 알면 된다.
새로운 요소가 들어오면 배열의 가장 마지막에 해당 요소를 push해 넣고 반복문을 진행한다. 반복문에서는 현재 자신의 index 값을 가지고(가장 마지막에 넣었기 때문에 배열의 길이를 통해서 자신의 index를 유추할 수 있다.) 자신 노드의 값과 부모노드의 값을 비교해서 자신 노드의 값이 더 크면 부모노드와 값을 바꿔준다.
해당 작업은 더 이상 부모노드와의 swap이 일어나지 않으면 반복을 종료한다.
