[프로그래머스 힙 Lv.3 디스크 컨트롤러] 저의 코드와 정답 코드의 비교...
-
게시물 수정 , 삭제는 로그인 필요
상단 코드는 저의 코드이고 하단 코드는 정답 코드입니다.
저의 처음 생각은 힙을 사용하지 말고 진행하는 것이었습니다. 굳이 필요없을 것 같더라구요. (저의 짐작...)
다음으로 시간 오름차순으로 jobs를 오름차순 정렬한 후 맨 처음 job을 처리하고 나서,
그 사이에 요청된 다른 job들이 있으면 그것들 중 최소의 소요시간(min)을 갖는 job을 선택하도록 했습니다.
또한 대기 시간이 0보다 작으면 현재시간(current)만 갱신하고, 0보다 크다면 대기시간을 더한 소요시간을 다시 push하여
최종적으로 대기시간까지 포함한 소요시간을 평균 내었습니다.
전체적인 흐름은 정답의 흐름과 비슷한 거 같은데 어떤 부분에서 미처 생각치 못한 부분이 있는지 고수님들의 고견 부탁드립니다.
P.S. 하단 정답 코드의 MinPriorityQueue는 직접 구현한 클래스입니다.
==============================================================
function solution(jobs) {
// 문제에 시간 오름차순 정렬된 채로 주어진다는 언급 없음
jobs = jobs.sort((a,b) => a[0]-b[0]);
// 초기 상태에서는 작업을 수행하지 않으므로 바로 시작
let progress = [];
let current = jobs[0][1];
progress.push(jobs.shift());
while(jobs.length > 0) {
// 소요 시간이 가장 짧은 작업 선택
let j = 0, min = jobs[j][1];
for(let i = 1; i < jobs.length; i++) {
if(jobs[i][0] <= current) {
if(min > jobs[i][1]) {
j = i;
min = jobs[j][1];
}
}
else break;
}
let on_process = jobs.splice(j, 1)[0]; // 요청 시간
let delay = current - on_process[0]; // 대기 시간
if(delay > 0) {
current += on_process[1];
on_process.push(delay + on_process.pop()); // 종료 시간
} else {
current += on_process[1] - delay;
}
progress.push(on_process);
}
//console.log(progress)
let sum = progress.reduce((acc, curr) => acc + curr[1], 0);
return ~~(sum / progress.length);
}
==============================================================
function solution(jobs) {
jobs.sort((a,b) => a[0]-b[0]);
let pqueue = new MinPriorityQueue();
let count = 0;
let index = 0;
let end = 0;
let total = 0;
while(count < jobs.length) {
while(index < jobs.length && jobs[index][0] <= end) {
pqueue.enqueue(jobs[index][0], jobs[index][1]);
index++;
}
pqueue.heap.sort((a,b) => a[1]-b[1]);
if(pqueue.isEmpty()) {
end = jobs[index][0];
} else {
let curr = pqueue.dequeue();
total += curr[1] + end - curr[0];
end += curr[1];
count++;
}
}
return ~~(total/jobs.length);
}
#프로그래머스 힙