[프로그래머스] 고득점 키트 - 힙1

오늘 푼 문제

 

1. 디스크 컨트롤러/ Lv.3/ 시간 : 53분(타임오버)

programmers.co.kr/learn/courses/30/lessons/42627?language=javascript

코딩테스트 연습 - 디스크 컨트롤러

function solution(jobs) {
    jobs.sort((a,b)=>a[1]-b[1]);
    const len = jobs.length;
    var answer = 0;
    let ct = 0; //current time
    let wt = 0; // whole time
    let task;  
    
    while(jobs.length){
        let index = jobs.findIndex(a=>a[0]<=ct);
        if(index===-1){
            ct++;
            continue;
        }
        task = jobs.splice(index,1)[0];
        ct += task[1];
        wt += (ct - task[0]);
    }
    
    answer = Math.floor(wt/len);
    
    return answer;
}

 

헤맸던 부분

1. 우선순위를 어떻게 고려해야 하는지 고민했는데 작업의 소요시간이 가장 짧은 애를 고르면 됨.

2. 이를 코드로 반영하기 위해 먼저

1) 현재 시점(ct)에서 착수 가능한 작업을 모두 추출해(작업이 요청되는 시점이 ct보다 같거나 작은 경우)

2) 이 중에서 소요시간이 가장 짧은 작업을 선택하는 방법

을 사용하려 했으나 반복이 너무 많이 사용되고, 착수 가능 작업 목록을 저장하는 공간이 추가로 필요하며, 작업 요청이 없어 붕 뜨는 시간까지 고려해야 하니 코드가 더러워짐.

 

이번에는 방향을 바꿔서

1) 요청시간을 기준으로 정렬되어 있는 작업 배열을 소요시간이 짧은 순으로 재정렬 함.

2) 이렇게 되면 요청시간이 섞이게 되니 매번 현재 시점을 기준으로 요청이 들어온 작업을 찾아주는 과정이 필요함. 

3) 그래도 findIndex를 사용면 조건을 충족하는 요소를 하나라도 발견하는 순간 뒷 배열을 순회하지 않고 반복을 종료하니 실 반복수를 줄일 수 있음.

4) 배열이 소요시간이 짧은 것 부터 정렬되어있으니 가장 먼저 발견된 작업이 곧 그 시점에서 최선의 작업이라는게 보장이 됨.

5) 또한 시간이 붕 뜨는 상황도 findIndex의 값이 -1이면 시간만 증가시킨다 정도로 간결하고 직관적으로 처리가 가능함.

6) 선택한 작업에 맞게 현재 시간과 작업에 걸린 시간 등을 알맞게 증가시키고 원본 배열에서 삭제만 해주면 되니 메모리 공간을 낭비하지 않음