🖋️ 프로그래머스 힙 (HEAP)

@ 더 맵게

• 모든 음식의 스코빌 지수를 K 이상으로 만들기위한 섞어야 하는 최소 횟수
• 스코빌 지수가 가장 낮은 두 개의 음식을 특별한 방법으로 섞어 새로운 음식 만들기
  • 섞은 음식의 스코빌 지수 = 가장 낮은 스코빌 지수 + (두 번째 낮은 스코빌 지수 * 2)
    
    
• 스코빌 지수를 담은 배열 scoville
• 원하는 스코빌 지수 K

• 좋은 풀이

class MinHeap {
  constructor() {
    this.heap = [];
  }
  
  size() {
    return this.heap.length;
  }
  
  peek() {
    return this.heap[0];
  }
  
  // 값 등록 후, 최소 힙이기 때문 오름차순 정렬
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;

    // 등록된 값의 위치 정렬될 때까지
    while (
      currentIndex > 0 &&
      this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
    ) {
      // swap 코드 
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
      this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
      currentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

  // 값 방출 후, 최소 힙이기 때문 오름차순 정렬
  pop() {
    if (this.heap.length === 0) return null;
    else if (this.heap.length === 1) return this.heap.pop();

    // 제일 큰 값을 idx 0 부터 재정렬
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    let currentIndex = 0;

    while (currentIndex * 2 + 1 < this.heap.length) {
      let minChildIndex = currentIndex * 2 + 2 < this.heap.length && this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1] ? currentIndex * 2 + 2 : currentIndex * 2 + 1;

      if (this.heap[currentIndex] < this.heap[minChildIndex]) {
        break;
      }

      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[minChildIndex];
      this.heap[minChildIndex] = temp;
      currentIndex = minChildIndex;
    }

    return minValue;
  }
}

function solution(scoville, K) {
    const minHeap = new MinHeap();
  
    // scoville 최소힙으로 정의
    for (const sco of scoville) minHeap.push(sco);
    
    let mixedCnt = 0;
  
    // 최소힙 사이즈가 2이상이며, 제일 작은 수가 K보다 작을 때
    while(minHeap.size() >= 2 && minHeap.peek() < K){
        const first = minHeap.pop();
        const second = minHeap.pop();
		const mixedFood = first + second * 2;
      
        minHeap.push(mixedFood);
        mixedCnt++;
    }
    
    return minHeap.peek() >= K ? mixedCnt : -1;
}

@ 디스크 컨트롤러

• 한 번에 하나의 작업만 수행
• 가장 일반적인 방법은 요청이 들어온 순서대로 처리
• 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리
• 각 작업의 요청부터 종료까지 걸린 시간의 평균
  
  
• [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs
• (단, 소수점 이하의 수는 버립니다)

• Heap 사용한 풀이

function solution(jobs) {
  const count = jobs.length;
  const minHeap = new MinHeap();
  jobs.sort((a,b) => a[0]-b[0]);
  
  let time = 0;
  let complete = 0;
  let total = 0;
  
  while(jobs.length || minHeap.size()) {
    while(jobs.length) {
      if(jobs[0][0] === time) {
        minHeap.push(jobs.shift());
      } else break;
    }
    
    if(minHeap.size() && time >= complete) {
      const task = minHeap.pop();
      complete = task[1] + time;
      total += complete - task[0];
    }
    time++;
  }
  
  return total / count >> 0;
}

class MinHeap {
    constructor() {
        this.heap = [ null ];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    getMin() {
        return this.heap[1] ? this.heap[1] : null;
    }
    
    swap(a, b) {
        [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
    }
    
    push(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        while(curIdx > 1 && this.heap[parIdx][1] > this.heap[curIdx][1]) {
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    
    pop() {
        const min = this.heap[1];	
        if(this.heap.length <= 2) this.heap = [ null ];
        else this.heap[1] = this.heap.pop();   
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1; 
        
        if(!this.heap[leftIdx]) return min;
        if(!this.heap[rightIdx]) {
            if(this.heap[leftIdx][1] < this.heap[curIdx][1]) {
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

        while(this.heap[leftIdx][1] < this.heap[curIdx][1] || this.heap[rightIdx][1] < this.heap[curIdx][1]) {
            const minIdx = this.heap[leftIdx][1] > this.heap[rightIdx][1] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
            
            if(leftIdx >= this.size()) break;
        }

        return min;
    }
}

• 더 효율적인 풀이

function solution(jobs) {
    jobs.sort(([a, b], [c, d]) => a - c || b - d);
    const waiting = [];
    const count = jobs.length;
    let processed_time = 0;
    let time = 0;
    while (jobs.length + waiting.length) {
        let in_process;
        while (jobs.length && (jobs[0][0] <= time)) {
            waiting.push(jobs[0] && jobs.shift());
        }
        if (waiting.length) {
            in_process = waiting.sort(([a, b], [c, d]) => b - d || a - c).shift();
        } else {
            in_process = jobs.shift();
            time = in_process[0];
        }
        time += in_process[1];
        processed_time += time - in_process[0];
    }
    return Math.floor(processed_time / count);
}