[힙] 배상 비용 최소화

Problem. 배상 비용 최소화

---

Link.

https://school.programmers.co.kr/learn/courses/13213/lessons/91086

프로그래머스

---

Problem.

OO 조선소에서는 태풍으로 인한 작업지연으로 수주한 선박들을 기한 내에 완성하지 못할 것이 예상됩니다.

기한 내에 완성하지 못하면 손해 배상을 해야 하므로 남은 일의 작업량을 숫자로 매기고 배상 비용을 최소화하는 방법을 찾으려고 합니다.

배상 비용은 각 선박의 완성까지 남은 일의 작업량을 제곱하여 모두 더한 값이 됩니다.

 

조선소에서는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다.

조선소에서 작업할 수 있는 N시간과 각 일에 대한 작업량이 담긴 배열(works)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요.

 

제한사항

1. 일할 수 있는 시간 N: 1,000,000 이하의 자연수

2. 배열 works의 크기: 1,000 이하의 자연수

3. 각 일에 대한 작업량: 1,000 이하의 자연수

 

입출력 예시

// case#1
N = 4;
works = [4, 3, 3];
-> works = [2, 2, 2];
-> 2*2 + 2*2 + 2*2 = 4 + 4 + 4 = 12

// case#2
N = 2;
works = [3, 3, 3];
-> works = [2, 2, 3];
-> 2*2 + 2*2 + 3*3 = 4 + 4 + 9 = 17

---

My Answer. 

class MaxHeap {
    constructor() {
        this.heap = [null];
    }
    
    push(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);
        
        while (parentIndex !== 0 && this.heap[parentIndex] < value) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = value;
            this.heap[currentIndex] = temp;
            
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }
    
    pop() {
    	// 정점이 루트만 남은 경우
        if (this.heap.length === 2) return this.heap.pop();
        
        let returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();
        
        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;
        
        while (
            this.heap[leftIndex] > this.heap[currentIndex] ||
            this.heap[rightIndex] > this.heap[currentIndex]
        ) {
            if (this.heap[leftIndex] < this.heap[rightIndex]) {
                const temp = this.heap[currentIndex];
                this.heap[currentIndex] = this.heap[rightIndex];
                this.heap[rightIndex] = temp;
                
                currentIndex = rightIndex;
            } else {
                const temp = this.heap[currentIndex];
                this.heap[currentIndex] = this.heap[leftIndex];
                this.heap[leftIndex] = temp;
                
                currentIndex = leftIndex;
            }
            leftIndex = currentIndex * 2;
            rightIndex = currentIndex * 2 + 1;
        }
        
        return returnValue;
    }
}

function solution(no, works) {
	// no 시간안에 남은 작업량을 모두 처리할 수 있는 경우
    if (works.reduce((a, b) => a + b) <= no) {
        return 0;
    };
    
    const heap = new MaxHeap();
    // MaxHeap에 남은 작업시간(work)을 추가
    for (const work of works) {
        heap.push(work);
    };
    // 남은 no 시간동안 작업시간이 긴 작업부터 1만큼 처리
    // 1. heap.pop() -1 => 작업시간이 가장 긴 루트 값을 빼낸 후 -1
    // 2. heap.push(1번 값) => 다시 MaxHeap 삽입
    for (let i = 0; i < no; i++) {
        heap.push(heap.pop() - 1);
    };
    // 남은 작업량을 기준으로 배상 비용을 계산해서 반환
    return heap.heap.reduce((acr, cur) => acr + cur * cur);
}

---

References.

• 코딩테스트 광탈 방지 A to Z: JavaScript (이선협)
• 자바스크립트 - reduce 메서드: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)