*모든 코드는 Javascript로 작성합니다.
*코드는 참고용으로만 봐주세요!
문제
https://programmers.co.kr/learn/courses/30/lessons/42627
코딩테스트 연습 - 디스크 컨트롤러
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를
programmers.co.kr
해결방법
< 특정 시점에 할 수 있는 일들 중 (해당 시점 이전에 요청이 들어온 일), 가장 소요 시간이 짧은 일을 선택한다.>
그 이유는 결과값 계산식을 세워보면 알 수 있다.
➡ a가 요청시간, b가 소요시간, c가 시작시간이라고 한다면 c+b가 종료 시간이다.
➡ 따라서 작업 하나 당 요청에서 종료까지 소요된 시간은 c+b-a.
➡ 여기서 a, b는 고정이므로 c를 줄이는게 중요하다.
➡ 모든 작업의 c값을 줄이는 방법은 소요시간이 짧은 것부터 빨리빨리 끝내버리는 것!
- 가장 소요 시간이 짧은 일을 빠르게 얻기 위해 힙(최소 힙)을 사용한다
- 메인 while loop에서는 매 시간마다 요청이 들어온 일들을 heap에 넣은 후, 할 수 있는 일들 중 소요 시간 짧은 일을 수행한다.
- 수행 후 종료 시간으로 시간 점프.
- loop은 각 일의 시작 시간을 모두 얻을 때까지 돌게끔 한다.
코드
|
class Heap{ //최소 힙
constructor(){
this.heap = [];
}
add(x){
this.heap.push(x);
var i = this.heap.length - 1;
while ( i > 0 ){
var p = Math.floor((i-1)/2);
if (this.heap[p] > x){
this.heap[i] = this.heap[p];
i = p;
}
else break;
}
this.heap[i] = x;
}
getHead(){
if (this.heap.length == 0) return false;
return this.heap[0];
}
removeHead(){
if (this.heap.length == 0) return false;
var head = this.heap[0];
if (this.heap.length == 1){
this.heap = [];
return head;
}
var x = this.heap.pop();
var i = 0;
while (2*i + 1 < this.heap.length){
var child_1 = 2*i + 1;
var child_2 = 2*i + 2;
if (this.heap[child_2] && this.heap[child_1] > this.heap[child_2]){
child_1 = child_2;
}
if (this.heap[child_1] < x){
this.heap[i] = this.heap[child_1];
i = child_1;
}
else break;
}
this.heap[i] = x;
return head;
}
isEmpty(){
if (this.heap.length == 0) return true;
return false;
}
}
function solution(jobs) {
var heap = new Heap;
var sortedByRT = [...jobs].sort((a, b)=>{ //시작 시간 빠른 순으로 sort
return a[0]-b[0];
})
var time = 0;
var startedTime = []; //각 일의 시작시간 담을 배열
var check = new Array(jobs.length); //이미 완료한 일 표시하기 위한 배열
check.fill(0);
while (startedTime.length < jobs.length){
//할 수 있는 일들 heap에 추가
for (let i = 0; i < sortedByRT.length; i++){
if (sortedByRT[i][0] <= time && check[i] == 0){ // 요청시간이 현재 시간보다 빠르고,
// 아직 완료하지 않았다면 heap에 추가 heap.add(sortedByRT[i][1]);
check[i] = 1;
}
if (sortedByRT[i][0] > time) break; // 시간 순으로 정렬했으므로 아닌 거 나오면 break
}
//비어 있으면 시간++
if (heap.isEmpty()){
time++;
continue;
}
//비어 있지 않으면 가장 빨리 끝나는 일 시작
var nextEnd = heap.removeHead();
startedTime.push(time);
time += nextEnd;
}
//전체 계산식 = 시작 시간 총합(a) + 걸리는 시간 총합(b)- 요청받은 시간(c) 총합 평균내기.
var b = 0, c = 0;
sortedByRT.forEach(([x, y])=>{
c+=x;
b+=y;
})
var a = startedTime.reduce((x, y)=>x+y);
var answer = Math.floor((a+b-c)/jobs.length);
return answer; }
|
'Coding test > programmers' 카테고리의 다른 글
| [프로그래머스] Lv.3 네트워크 (자바스크립트) (0) | 2022.07.01 |
|---|---|
| [프로그래머스] Lv.3 여행경로 (자바스크립트) (0) | 2022.06.30 |
| [프로그래머스] Lv.3 입국심사 (자바스크립트) (0) | 2022.06.30 |