[프로그래머스💯] 코딩테스트 연습 > 힙(Heap) > 디스크 컨트롤러

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

const solution = jobs => {
  let jobsLen = jobs.length
  let totalTime = 0
  let nowTime = 0
  jobs = jobs.sort((arr1, arr2) => {
    return arr1[0] - arr2[0]
  }) // jobs 를 시작시간 기준으로 sort 해준다.

  while (jobs.length != 0) {
    const { startTime, spendTime, remainArr } = 
   	getSecondIndexMin(jobs, nowTime)
    nowTime = Math.max(nowTime + spendTime, startTime + spendTime)
    totalTime += nowTime - startTime
    jobs = remainArr
  }

  return Math.floor(totalTime / jobsLen)
}

const getSecondIndexMin = (arr, nowTime) => {
  let min = Infinity
  let minIndex = 0
  let index = 0
  for (let a of arr) {
    if (a[1] < min && a[0] <= nowTime) {
      min = a[1]
      minIndex = index
    }
    index += 1
  }
  if (min === Infinity) { // nowTime > a[0] 일때
    var st = arr[0][0]
    index = 0
    while (index < arr.length) {
      console.log("while문")
      if (arr[index][0] !== st) break
      if (arr[index][1] < min) {
        min = arr[index][1]
        minIndex = index
      }
      index += 1
    }
  }
  const startTime = arr[minIndex][0]
  const spendTime = arr[minIndex][1]
  arr.splice(minIndex, 1)
  return {
    startTime,
    spendTime,
    remainArr: arr
  }
}

 

 

풀이)

 

알고리즘 : 

 

이 문제의 해결법은 그리디 알고리즘에 속합니다.

현재 시각에서 할 수 있는 작업 중, 가장 소요시간이 조금 걸리는 일을 하면됩니다.

이걸 작업이 없을때 까지 계속 반복하면됩니다.

하지만, 중요한 조건은, 현재 아무작업도 들어와있지 않은순간이라면, 가장먼저 들어오는 작업을 해야 합니다. (작업이 동시에 들어오면 가장 빨리끝나는 작업 먼저)

 

---

getSecondIndexMin 함수(작업들, 현재시각)

 

Input : 작업의 목록들과 현재 시각을 받습니다.

 

Output : 시작시간, 소요시간, 현재 상황에서 베스트인 작업을 하고 난 뒤의 작업들을 반환합니다.