[프로그래머스] 디펜스 게임 (JS)

풀이 과정

최대힙

• enemy 배열에 대해 반복하면서 라운드를 진행
• n이 음수가 되면 최대힙에서 이전 라운드 중 가장 많았던 병사 수를 꺼내 n에 더해주고 무적권 수 감소

코드

function solution(n, k, enemy) {
  let result = 0;
  const heap = new MaxHeap();
  for (const e of enemy) {
    heap.push(e);
    n -= e;
    if (n < 0) {
      if (k <= 0) break;
      n += heap.pop();
      --k;
    }
    ++result;
  }
  return result;
}

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

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

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  push(v) {
    this.heap.push(v);
    let i = this.size() - 1;
    let parentI = Math.floor((i - 1) / 2);
    while (i > 0 && this.heap[i] > this.heap[parentI]) {
      this.swap(i, parentI);
      i = parentI;
      parentI = Math.floor((i - 1) / 2);
    }
  }

  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

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

    let i = 0;
    while (i < this.size()) {
      const leftI = i * 2 + 1;
      const rightI = i * 2 + 2;
      let big = leftI;
      if (rightI < this.size() && this.heap[leftI] < this.heap[rightI]) {
        big = rightI;
      }
      if (this.heap[big] > this.heap[i]) {
        this.swap(big, i);
      }
      i = big;
    }

    return maxV;
  }
}

🤔

처음에 DFS로 구현했는데, 하면서도 안 될 건 알았지만 제출하니 모두 시간초과 ㅎㅎㅎ
힌트를 보고 최대힙 방식으로 풀었다.
이전 라운드 중에서 가장 많았던 병사 수를 순차적으로 꺼내야 하니까 최대힙이 효율적이다.
힙 구현을 또 까먹어서 이전에 풀었던 문제를 참고해서 구현했다.