[프로그래머스]힙(Heap) 디스크 컨트롤러

임택·2021년 1월 20일
0

알고리즘

목록 보기
16/63

Problem



code

const log = console.log;
function solution(jobs) {
    // 작업 갯수
    const jobsLen = jobs.length;
    
    // jobs 도착 시간별로 소팅
    jobs.sort((j1, j2) => j1[0] - j2[0]);
    
    // disk
    let disk = 0;
    
    // 대기큐
    const waitQ = [];
    
    // 시작부터 흐른 시간
    let t = 0;
    
    // 걸린 시간
    let total = 0;
    
    //if disk empty, jobs에 첫 번째 작업 실행 if jobs.length != 0
    while (jobs.length > 0 || waitQ.length > 0)
    {
        // t보다 작은 작업들을 찾아 waitQ에 적재
        while (jobs.length > 0 && jobs[0][0] <= t)
        {
            waitQ.push(jobs.shift());
        }


        // log(waitQ, 'disk', disk, 't', t, 'total', total);
        if (disk == 0) // 디스크 작업 없을 때
        {
            // 기다리는 작업이 있을 때
            if (waitQ.length > 0)
            {
                // SJF을 위해 작업시간으로 오름차순 정렬
                waitQ.sort((j1, j2) => j1[1] - j2[1]);    
                
                // waitQ에서 작업을 가져와 disk에 적재
                const next = waitQ.shift();
                
                
                const arrivalT = next[0];
                const workingT = next[1];
                // next 작업 도착 시간 next[0]가 흐른 시간 t <=을 때 작업 시작
                disk = workingT - 1;
                
                // 시작하면 작업 1초 지나가니까
                total++;
                
                // 흐른 시간에서 도착 시간을 빼면 기다린 시간
                total += t - arrivalT;
            }
        }
        else // 디스크 작업 중일 때
        {
            // 남은 작업 시간 감소
            disk--;
            // 작업 진행시간 반영
            total++;
        }
        
        // 흐르는 시간 계산
        t++;
        
    }
    
    if (disk) total += disk;

    // javascript 나누기 후 소수점 처리
    return parseInt(total/jobsLen);
}
profile
캬-!

0개의 댓글