LeetCode / Heap / 502번 / IPO / JS

< 문제 간단설명 >

LeetCode가 IPO를 앞두고 자본을 최대화하기 위해 최대 k개의 프로젝트를 선택하여 완료하려고 한다.

각 프로젝트는 특정 이익(profits)과 시작하기 위해 필요한 최소 자본(capital)을 가지고 있다.

초기 자본(w)로 시작하여 프로젝트를 선택하고, 선택한 프로젝트의 이익을 총 자본에 추가한다.

최대 k개의 프로젝트를 선택하여 최종 자본을 최대화하는 방법을 찾아야 한다.

최종 최대 자본을 반환하면 되는 문제이다.

 

< 코드 >

/**
 * @param {number} k 선택할 프로젝트의 최대 개수
 * @param {number} w 초기 자본
 * @param {number[]} profits 순수 이익
 * @param {number[]} capital 시작하기 위해 필요한 최소 자본
 * @return {number} 최종 최대 자본
 */
var findMaximizedCapital = function (k, w, profits, capital) {
  // 각 프로젝트를 [자본, 이익] 형태로 저장한다.
  let projectList = profits.map((profit, index) => [capital[index], profit]);

  // 프로젝트를 시작 자본 기준으로 정렬한다.
  projectList.sort((a, b) => a[0] - b[0]);

  let maxHeap = new MaxHeap();
  let i = 0;

  for (let j = 0; j < k; j++) {
    // 현재 자본으로 시작할 수 있는 모든 프로젝트를 힙에 삽입한다.
    while (i < projectList.length && projectList[i][0] <= w) {
      // 이익을 힙에 삽입한다.
      maxHeap.insert(projectList[i][1]);
      i++;
    }

    // 힙에서 가장 큰 이익을 얻을 수 있는 프로젝트를 선택한다.
    if (maxHeap.size() > 0) {
      w += maxHeap.extractMax();
    } else {
      // 더 이상 시작할 수 있는 프로젝트가 없을 경우 중지한다.
      break;
    }
  }

  return w;
};

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

  /** 새로운 값을 힙에 추가 */
  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  /** 삽입된 값이 올바른 위치에 있을 때까지 상위로 이동 */
  bubbleUp(index) {
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[parentIndex] >= this.heap[index]) {
        break;
      }

      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  /** 힙의 최상단 값을 제거한 후, 마지막 값을 최상단으로 이동 */
  extractMax() {
    if (this.size() === 1) {
      return this.heap.pop();
    }

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);

    return max;
  }

  /** 최상단 값이 올바른 위치에 있을 때까지 하위로 이동 */
  bubbleDown(index) {
    while (true) {
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      let largest = index;

      if (
        leftChild < this.size() &&
        this.heap[leftChild] > this.heap[largest]
      ) {
        largest = leftChild;
      }
      if (
        rightChild < this.size() &&
        this.heap[rightChild] > this.heap[largest]
      ) {
        largest = rightChild;
      }

      if (largest === index) {
        break;
      }

      [this.heap[index], this.heap[largest]] = [
        this.heap[largest],
        this.heap[index],
      ];
      index = largest;
    }
  }

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

 

< MaxHeap 사용 이유 >

1. 최대 이익 프로젝트 선택
   • MaxHeap은 삽입과 삭제 연산 모두 O(log n)의 시간 복잡도를 가지므로 효율적이다.
   • 현재 자본으로 시작할 수 있는 모든 프로젝트를 힙에 넣고, 그 중 가장 큰 이익을 가지는 프로젝트를 빠르게 선택할 수 있다.
2. 효율적인 연산
   • 프로젝트를 선택할 때마다 남은 자본을 고려해야 하므로, 각 단계에서 최대 이익을 얻을 수 있는 프로젝트를 선택하는 것이 중요하다.
   • MaxHeap을 사용하면 이 과정을 빠르게 수행할 수 있어 전체 알고리즘의 효율성을 높일 수 있다.