[JS] 디스크 컨트롤러 - 왜 이 문제는 힙을 써야하는지 알랴드림!

이 문제는 유형 분류에도 힙으로 되어있지만,

전 일단 청개구리 마인드가 있는지... 일단 이런거 있으면 제 생각대로 한 번 해보거든여

이러면 일단 왜 꼭 이 자료구조나 방법을 써야하는지 감도 잡히고, 그 자료 구조가 어떤 상황에서 유리한지 익힐 수 있어서 좋은 방법이 아닌가 생각이 듭니다.

스택으로 해볼때 힙 쓰면 금방할 줄 알고 이렇게 썼는데 그냥 힙으로 쓰세요. 진짜 인생 피곤하네요 이문제 하하 

 

아무튼 디스크 컨트롤러 시작합니다! 같이 한 번 보시죠!

---

문제 요약

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 작업의 요청부터 종료까지 걸린 시간이 최소가 되게끔 하는 방법은 다음과 같습니다.

 

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

 

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

 

테스트케이스

jobs	return
[[0, 3], [1, 9], [2, 6]]	9

 

접근 방법

코테는 국어문제다. 라는 느낌이 드는 문제네요.

작업의 요청부터 종료까지 걸린 시간의 평균이 중요합니다. 조금만 생각해보면 어떻게 해야할 지 어렴풋이 감이 오는데요.

결론적으론 작업 시간이 긴 작업일 수록 뒤에 하는게 유리합니다.

왜냐하면 변수로 나오는 대기시간이 순전히 앞의 작업의 소요시간에만 영향을 받기 때문입니다. 앞의 작업 소요시간이 짧으면 짧을 수록 대기시간이 줄기 때문에 비교적 논리는 간단하네요. 매번 요소를 넣을 때마다 정렬해주면 됩니다.

 

다만! 여기서 무지성으로 stack 배열을 만든 다음 정렬을 해준다면 시간초과가 납니다.

두 가지 솔루션을 준비했습니다. 방법 1은 시간초과가 납니다. 공부용으로 참고하면 좋을 것 같습니다.

 

1. 스택(배열)에 작업을 넣고 작업이 들어갈 때마다 정렬해주는 방법(정렬에 O(N)이 걸립니다.)
2. 힙을 이용해 효율적인 정렬을 해주는 방법(정렬에 O(logN)이 걸립니다.)

힙은 제가 얼마전에 자료구조로 공유해드린 적이 있죠. 한 번 보시면 좋을 것 같습니다. 

2022.08.03 - [자료구조] - [JS] 힙(Heap) - 큐 외길인생에서 힙을 만나다.

[JS] 힙(Heap) - 큐 외길인생에서 힙을 만나다.

 

자 같이 보시죠!

solution 1(스택) - 오답

function solution(jobs) {
    const n = jobs.length;
    let scheduler = [];
    let timer = 0;
    let complete = 0;
    let taskEndTime = 0;
    let answer = 0;
    
    while (true) {
        if (complete < n) {
            const currJobs = jobs.filter(v => v[0] === timer);
            scheduler.push(...currJobs);
            scheduler.sort((a, b) => b[1] - a[1]);
            complete += currJobs.length;
        }
        if (scheduler.length > 0 && taskEndTime === timer) {
            const [start, time] = scheduler.pop();
            answer += time + timer - start;
            taskEndTime = timer + time;
        }
        if (complete === n && scheduler.length === 0) break;
        timer++;
    }
    
    return Math.floor(answer / n);
}

 

결과

 

solution 2(힙) - 정답

class Heap {
	constructor() {
    	this.heap=[null];
    }
    
    push(value) {
    	this.heap.push(value);
        let currIdx = this.heap.length - 1;
        let parentIdx = Math.floor(currIdx / 2);
        
        while(parentIdx > 0 && this.heap[parentIdx][1] > value[1]) {
            [this.heap[parentIdx], this.heap[currIdx]] = [this.heap[currIdx], this.heap[parentIdx]];
            
            currIdx = parentIdx;
            parentIdx = Math.floor(currIdx / 2);
        }
    }
    
    pop() {
        if (this.heap.length === 2) return this.heap.pop();
        
    	const val = this.heap[1];
        this.heap[1] = this.heap.pop();
        
        let currIdx = 1;
        let pl = currIdx * 2;
        let pr = currIdx * 2 + 1;
        
        if (!this.heap[pl]) return val;
        if (!this.heap[pr]) {
            if (this.heap[pl][1] < this.heap[currIdx][1])
                [this.heap[currIdx], this.heap[pl]] = [this.heap[pl], this.heap[currIdx]];
            return val;
        }
            
        while(this.heap[currIdx][1] > this.heap[pl][1] ||
              this.heap[currIdx][1] > this.heap[pr][1]) {
            if (this.heap[pl][1] > this.heap[pr][1]) {
                [this.heap[currIdx], this.heap[pr]] = [this.heap[pr], this.heap[currIdx]];
                currIdx = pr;
            } else {
                [this.heap[currIdx], this.heap[pl]] = [this.heap[pl], this.heap[currIdx]];
                currIdx = pl;
            }
            pl = currIdx * 2;
            pr = currIdx * 2 + 1;
            if (pl >= this.heap.length - 1) break;
        }
        return val;
    }
}

function solution(jobs) {
    const n = jobs.length;
    const scheduler = new Heap();
    jobs.sort((a, b) => b[0] - a[0]);
    let timer = 0;
    let complete = 0;
    let answer = 0;
    
    while (jobs.length > 0 || scheduler.heap.length > 1) {
        while (jobs.length) {
            if (jobs[jobs.length - 1][0] === timer) {
                scheduler.push(jobs.pop());
            } else break;
        }
        
        if (scheduler.heap.length > 1 && timer >= complete) {
            const [start, time] = scheduler.pop();
            complete = time + timer;
            answer += complete - start;
        }
        timer++;
    }
    
    return Math.floor(answer / n);
}

 

결과

 

팁 1. 런타임 에러가 자주날 수 밖에 없는 이유

while(parentIdx > 0 && this.heap[parentIdx][1] > value[1]) {
    [this.heap[parentIdx], this.heap[currIdx]] = [this.heap[currIdx], this.heap[parentIdx]];

    currIdx = parentIdx;
    parentIdx = Math.floor(currIdx / 2);
}

Heap 클래스의 push 함수의 일부입니다.

저번 포스트에서 제가 정의한 heap과 약간 다른 점이 있다면, 이전에는 단순히 number를 heap에 넣었기 때문에 크게 걱정할 게 없었지만, 이번엔 배열이 들어가기 때문에 index와 관련해서 에러가 나기 정말 쉽습니다.

 

만약 런타임 에러가 계속 난다거나 별로 틀린게 없는거 같은데 계속 실패가 나온다면 그건 아마 힙에 넣은 배열의 첫 번째 인덱스 요소를 비교하지 않거나 한 이유일 거겁니다.

 

계속 temp를 만들어서 넣어주다가 너무 코드가 길어져서 swap은 그냥 구조분해 할당으로 넣어줬습니다. 함수로 만들어서 호출하셔도 됩니다.

 

팁 2. pop의 분기가 많은 이유

if (!this.heap[pl]) return val;
if (!this.heap[pr]) {
    if (this.heap[pl][1] < this.heap[currIdx][1])
        [this.heap[currIdx], this.heap[pl]] = [this.heap[pl], this.heap[currIdx]];
    return val;
}

부모 노드와 자식 노드를 비교하는 로직 이전에 분기가 두 개 더 있습니다.

이진 트리를 기본으로 생각하고 짰기 때문에 (현재 index) = 1, (왼쪽 자식 index) = 2, (오른쪽 자식 index) = 3로 가정하고 넘어가는 부분이 있었습니다만,, 만약 heap의 요소를 하나만 push한 경우가 문제가 됩니다.

heap = [null, [0, 1]];
let [pl, pr] = [2, 3];

// this.heap[pl][1] X
// this.heap[pr][1] X

 

이런 상태였을 때 원래 정의하던 pl = 2, pr = 3 으로 접근하면 undefined 요소에서 index를 접근하기 때문에 아예 런타임 오류가 납니다. 이거 신경쓰는게 진짜 어려워요. 특히 pop() 함수가 가뜩이나 분기가 많은데 가독성 좋게 짜기가 쉽지 않습니다.

 

팁 3. answer과 complete의 상관관계

let timer = 0;
let complete = 0;
let answer = 0;

while (jobs.length > 0 || scheduler.heap.length > 1) {
    while (jobs.length) {
        if (jobs[jobs.length - 1][0] === timer) {
            scheduler.push(jobs.pop());
        } else break;
    }

    if (scheduler.heap.length > 1 && timer >= complete) {
        const [start, time] = scheduler.pop();
        complete = time + timer;
        answer += complete - start;
    }
    timer++;
}

 

루프 안에서 timer는 계속 1씩 증가합니다.

만약 해당 시간대에 요청이 들어온다면, 모든 요소들을 heap에 push해줍니다.

complete는 지금 수행중인 작업의 종료시간을 의미합니다.

만약 지금 timer가 해당 작업의 종료시간이라면, 새로운 작업을 할당(scheduler에서 pop 해옵니다.)하고 다시 complete를 갱신해줍니다.

예시 사진을 보면 이해가 더 쉽습니다. 각 작업의 요청시간부터 종료시간까지는 전체 timer에서 요청 시간을 뺀 값과 동일하기 때문에 적절히 조절해주면 가능합니다.

 

정말... 힙 어렵네요.

그래도 이문제는 가치 있었습니다. number가 아닌 다중 배열을 힙에 넣는 경우 index와 관련해서 많이 조작해줘야하는데 만약 실전에서 이런거 만났다간 바로 3시간 녹을 것 같아요....ㅠ

그나마 지금 만나서 다행이네요! 여러분들도 안된다고 조급해하지 마시고 어떤게 본인 코드랑 다른지 비교해보고 깨달음을 얻으시길 바랍니다.

 

그럼 이만!