프로그래머스 코딩테스트 - 디스크 컨트롤러

2024.11.29 - [프로그래머스 데브코스: 클라우드 기반 웹 프론트엔드 3기] - Javascript로 Heap을 구현해보자

Javascript로 Heap을 구현해보자

지난 포스팅 내용인 heap 자료구조를 사용하는 가장 대표적인 예시인 스케줄링과 관련있는 문제라 선택해서 풀어봤다.

 

문제 설명

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

프로그래머스

 

해결 방법

아이디어

일단 중요한 것은 대기 큐에 들어간 작업은 작업 시간이 짧은 순서대로 꺼내서 작업을 진행한다는 것이다.

따라서 위 포스팅에서 제작한 최대 힙 클래스에서 부호를 반전시켜 최소 힙 클래스를 제작해야 한다.

 

• 스케줄 정렬 (jobs가 순서대로 들어오지 않는 경우도 있음)
• heap과 jobs가 빌 때까지 반복
  • jobs에서 현재 시간과 시작 시간이 동일한 작업 heap에 추가
  • 직전 작업이 종료된 후
    • heap에서 새로운 작업 꺼내서
    • 종료 시간을 계산하고
    • 소요 시간 계산

코드

class MinHeap {
  constructor() {
    this.heap = [0];
  }

  size() {
    return this.heap.length - 1;
  }

  swap(idx1, idx2) {
      [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }

  push(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  pop() {
    if (this.heap.length === 2) {
      return this.heap.pop();
    }

    const value = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.bubbleDown();
    return value;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIdx = Math.floor(index / 2);
    while (
      this.heap[parentIdx] &&
      this.heap[index][1] < this.heap[parentIdx][1]
    ) {
      this.swap(index, parentIdx);
      index = parentIdx;
      parentIdx = Math.floor(index / 2);
    }
  }

  bubbleDown() {
    let index = 1;
    let leftIdx = index * 2;
    let rightIdx = index * 2 + 1;

    while (
      (this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
      (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])
    ) {
      let smallerIdx = leftIdx;
      if (
        this.heap[rightIdx] &&
        this.heap[rightIdx][1] < this.heap[smallerIdx][1]
      ) {
        smallerIdx = rightIdx;
      }

      this.swap(index, smallerIdx);
      index = smallerIdx;
      leftIdx = index * 2;
      rightIdx = index * 2 + 1;
    }
  }
}

function solution(jobs) {
    const len = jobs.length;
    const heap = new MinHeap();
    
    let answer = 0;
    let end = 0;
    let time = 0;
    
    jobs.sort((a,b) => a[0]-b[0]);

    while (heap.size() || jobs.length) {
        while(jobs.length && jobs[0][0] === time) {
            heap.push(jobs.shift());
        }
    
        if(heap.size() && time >= end) {
            const task = heap.pop();
            end = task[1] + time;
            answer += end - task[0];
        }
        time++;
    }
    
    return Math.floor(answer / len)
}