들어가며

프로그래머스 문제 중 Heap 문제를 거의 안풀었다는 사실을 깨닫고 가볍게 풀어봤다. Heap 알고리즘은 최대, 최소 값을 찾을 때 logN 으로 찾을 수 있다. 하지만 javascript는 우선순위 큐나 heapq를 지원하지 않아서 문제 풀이가 힘들어진다.

이번 문제도 최대, 최소 값을 찾는 경우였다. 우선순위 큐를 쓰는 방식을 까먹어서 조금 해맸기에 글을 쓴다.

해설

처음은 큐를 2개 운용할 생각을 못하고 작업이 끝날 때 마다 jobs 배열을 slice해서 우선 순위 정렬 후 처리하려고 했다. 그렇게 해도 괜찮은데 구조적으로 너무 복잡해지더라. 시간 제한을 1시간 두고 푸는 연습을 하니까 마음만 급해져서 방향을 잘못잡았다. 결국 다 엎고 다시 만들게 됐다.

순서대로 들어온 작업이 있고 우선 순위(작업 소요 시간)가 주어진다. 사실 priorityQueue 조작을 Heap을 사용해야 logN으로 처리할 수 있다. 여기선 자체 정렬 알고리즘을 매번 실행해서 NlogN으로 실행하게 됐다. 보완을 한다면.. Heap으로 구현해야 된다. Heap 문제인데 Heap으로 풀면 효율성은 개선되지만 문제 푸는 시간이 부족하다니 아이러니하다.

첫 if문에서 timer만큼 jobs 배열에서 인덱스를 움직여서 우선순위 큐에 넣어준다. 내부에 continue 구문이 있어서 조건을 충족할 때까지 반복한다.

if문이 끝나면 여기서 우선순위 큐의 정렬이 발생하고 (NlogN) 가장 우선순위가 높은 작업을 실행한다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42627

function solution(jobs) {
  let answer = 0,
    jobsIdx = 0,
    timer = 0;
  jobs.sort((a, b) => a[0] - b[0]);

  const priorityQueue = [];
  while (jobsIdx < jobs.length || priorityQueue.length > 0) {
    // * timer가 흐른만큼 priorityQueue 배열에 push, jobsIdx 진행
    // * jobs[jobsIdx][0] 값이 timer보다 작을 때까지 반복
    if (jobsIdx < jobs.length && jobs[jobsIdx][0] <= timer) {
      priorityQueue.push(jobs[jobsIdx]);
      jobsIdx++;
      continue;
    }
    // * 우선순위 큐 정렬
    priorityQueue.sort((a, b) => a[1] - b[1]);
    // * 우선순위 큐에서 하나씩 값을 빼면서 timer, answer 값 변경
    if (priorityQueue.length > 0) {
      timer += priorityQueue[0][1];
      answer += timer - priorityQueue[0][0];
      priorityQueue.shift();
    } else {
      timer = jobs[jobsIdx][0];
    }
  }
  return parseInt(answer / jobs.length);
}

참고 URL

https://kyun2da.github.io/2020/07/21/diskController/