시작하며 🔥

예... 힙으로 풀었습니다만...

힙을 공부하고 싶어서 시작하다가 불맛을 봤습니다. 🥺
물론 테스트 케이스도 작겠다, 대충 어찌하면 시간 초과 내에 그냥 깔끔한 코드로 작성할 수 있겠다 싶었는데, 우리의 자바스크립트는 heap 자료구조를 제공하지 않는다네요...?

결국 하나하나 힙을 이해하고 짜면서 구현했습니다...!!
결과는 140줄. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 🤣😂

코드마저 깔끔하지 않아 만족스럽지는 않아요. 다만

최대한 힙을 이해하려 했음에, 그리고 이제는 안보고 구현할 수 있음에 만족하렵니다 🖐🏻

나중에 진짜 우선순위 큐를 만들어야 하면, sort 범벅을 만들면서 시간복잡도를 늘리지 않아도 되니까요. 😏

설계 과정

크게 다음과 같은 생각을 갖고 구현했습니다.

1. 살짝 그리디와 비슷한 생각을 해보자. 결국 전체 평균을 줄이는 방법은 가장 작업시간이 빠른 걸 먼저 처리하면 된다
2. 다만 예외조건인 지금 처리할 게 없으면 가장 빠른 것을 처리한다를 고려한다.
3. 따라서 결국에는 현재 처리할 게 있을 때 / 없을 때로 나눈다.
4. 현재 처리할 게 있다면 가장 작은 걸 계산하고, 나머지는 다시 우선순위큐에 삽입
5. 만약 당장 처리할 게 없다면 계속해서 나올 때까지 계산한다.
6. 이때 혹여나 지금 처리할 게 없다고 나올 때를 대비해서, minStart, minStartPeriod라는 변수로 가장 작업시간이 빠른 걸 메모한다.
7. 그러다 arr에 아무것도 없고, minHeap에 null 밖에 없다면 현재 모두 처리됐거나, minStart, minStartPeriod로 저장되어있을 것이다. 계산해서 리턴하자.

사실상 거의 구현에 집중했던 문제...😵

코드

class Heap {
    constructor() {
        this.heap = [ null ];
    }
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    updateParentIndex(nowIndex) {
        return Math.floor(nowIndex / 2);
    }
    updateIndicies(minIndex) {
        return [ minIndex, minIndex * 2, minIndex * 2 + 1]
    }
    filterPossibleJob(time) {
        return this.heap.filter(([start, end]) => time >= start)
    }
    getLength() {
        return this.heap.length;
    }
    print() {
        console.log(this.heap)
    }
}

class MinHeap extends Heap {
    constructor() {
        super(Heap);
    }
    heappush(value){
        this.heap.push(value);
        let nowIndex = this.heap.length - 1;
        let parentIndex = this.updateParentIndex(nowIndex);
        while(nowIndex > 1 && this.heap[nowIndex][1] <= this.heap[parentIndex][1]) {
            if (this.heap[nowIndex][1] === this.heap[parentIndex][1] && this.heap[nowIndex][0] < this.heap[parentIndex][0]) {
                return;
            }
            this.swap(nowIndex, parentIndex);
            nowIndex = parentIndex;
            parentIndex = this.updateParentIndex(nowIndex);
        }
    }
    heappop(){
        const min = this.heap[1];
        if (this.heap.length === 1) return;
        if (this.heap.length === 2) return this.heap.pop();
        else this.heap[1] = this.heap.pop();
        let [ nowIndex, leftIndex, rightIndex ] = this.updateIndicies(1);
        if(!this.heap[leftIndex]) return min;
        if(!this.heap[rightIndex]) {
            if (this.heap[leftIndex][1] < this.heap[nowIndex][1]) {
                this.swap(leftIndex, nowIndex)
            }
            return min;
        }
        while(this.heap[leftIndex][1] < this.heap[nowIndex][1] || this.heap[rightIndex][1] < this.heap[nowIndex][1]) {
            let minIndex;
            if (this.heap[leftIndex][1] < this.heap[rightIndex][1]) minIndex = leftIndex;
            else if (this.heap[leftIndex][1] > this.heap[rightIndex][1]) minIndex = rightIndex;
            else {
                if (this.heap[leftIndex][0] <= this.heap[rightIndex][0]) minIndex = leftIndex;
                else minIndex = rightIndex
            }
            this.swap(minIndex, nowIndex);
            [ nowIndex, leftIndex, rightIndex ] = this.updateIndicies(minIndex);
            if(!this.heap[leftIndex]) return min;
            if(!this.heap[rightIndex]) {
                if (this.heap[leftIndex][1] < this.heap[nowIndex][1]) {
                    this.swap(leftIndex, nowIndex)
                }
                return min;
            }
        }
        return min;
    }
}

const solution = (jobs) => {
    const heappushArr = () => {
        while (arr.length) minHeap.heappush(arr.pop())
    }
    const initializeMinStart = (start = Infinity, period = Infinity) => {
        [ minStart, minStartPeriod ]  = [ start, period ]
    }
    // return: totalTime
    let totalTime = 0;
    // 소요시간: time
    let time = 0;

    const minHeap = new MinHeap();
    jobs.forEach(job => minHeap.heappush(job));

    // 만약 현재 처리되어 있지 않을 경우 계산을 대비한 변수
    let [ minStart, minStartPeriod ] = [ Infinity, Infinity ];
    let arr = [];
    while (true) {
        if (minHeap.getLength() === 1 && arr.length === 0) {
            const result = (minStart !== Infinity) ? (totalTime + minStartPeriod) : totalTime;
            return Math.floor(result / jobs.length);
        }
        // 만약 모든 일들이 다 처리될 수 없는 상태라면 그냥 다시 minHeap에 넣어줌.
        if (arr.length > 0 && minHeap.getLength() === 1) {
            if (minStart) {
                time = minStart + minStartPeriod;
                totalTime += time - minStart;
            }
            heappushArr();
            initializeMinStart();
            continue;
        };
        // 조건을 만족하면 time, totalTime 요구조건에 맞춰 업데이트
        let [ start, period ] = minHeap.heappop();
        if (start <= time) {
            time += period;
            totalTime += time - start;
            heappushArr();
        }
        // 조건을 만족하지 못한다면, 만족할 때까지 pop
        else {
            initializeMinStart(start, period)
            // 빼내온 값의 start가 time보다 짧거나 다빼오지 않는 이상 계속 실행
            while (minHeap.getLength() !== 1) {
                let [ start, period ] = minHeap.heappop();
                // 나올 경우 계산
                if (start <= time) {
                    time += period;
                    totalTime += time - start;
                    if (minStart !== Infinity) arr.push([ minStart, minStartPeriod ])
                    heappushArr();
                    initializeMinStart();
                    break;
                }
                // 나오지 않는다면 계속 계산!
                else {
                    if (start < minStart) {
                        //일단 이전 minStart, minStartPeriod는 다시 넣어줘야 함.
                        arr.push([ minStart, minStartPeriod ]);
                        initializeMinStart(start, period);
                    }
                    else arr.push([ start, period ]);
                }
            } 
        }
    }
}