🖋️ 디펜스 게임

# 문제 설명

보유한 병사 n명으로 연속되는 적의
공격을 순서대로 최대 라운드까지 막는 게임

• 조건
  

  • 처음에 병사 n명
  • 매 라운드마다 enemy[i]마리의 적이 등장
  • 남은 병사 중 enemy[i]명 만큼 소모하여
    enemy[i]마리의 적을 막기 가능
    • 남은 병사가 7명이고, 적의 수가 2마리인 경우,
      현재 라운드를 막으면 7 - 2 = 5명의 병사가 남음
    • 남은 병사의 수보다 현재 라운드의 적의 수가
      더 많으면 게임이 종료
  • 게임에는 무적권이라는 스킬이 있으며,
    무적권을 사용하면 병사의 소모없이
    한 라운드의 공격을 막기 가능
  • 무적권은 최대 k번 사용 가능

• 매개 변수
  

  • 처음 가지고 있는 병사의 수n
  • 사용 가능한 무적권의 횟수 k
  • 매 라운드마다 공격해오는 적의 수가
    순서대로 담긴 정수 배열 enemy

• 반환값
  

  • 준호가 몇 라운드까지 막을 수 있는지 return

• 📢 제한사항

  • 1 ≤ n ≤ 1,000,000,000
  • 1 ≤ k ≤ 500,000
  • 1 ≤ enemy의 길이 ≤ 1,000,000
  • 1 ≤ enemy[i] ≤ 1,000,000
  • enemy[i]에는 i + 1 라운드에서
    공격해오는 적의 수가 담겨있음
  • 모든 라운드를 막을 수 있는 경우에는
    enemy[i]의 길이를 return

• 📰 입출력 예시

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

• CODE

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 currentIndex = this.size() - 1;
    let parentIndex = Math.floor((currentIndex - 1) / 2);
    while (currentIndex > 0 && this.heap[currentIndex] > this.heap[parentIndex]) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

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

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

    let currentIndex = 0;
    while (true) {
      const leftIndex = currentIndex * 2 + 1;
      const rightIndex = currentIndex * 2 + 2;
      let largestIndex = currentIndex;

      if (leftIndex < heapSize && this.heap[leftIndex] > this.heap[largestIndex]) {
        largestIndex = leftIndex;
      }
      if (rightIndex < heapSize && this.heap[rightIndex] > this.heap[largestIndex]) {
        largestIndex = rightIndex;
      }
      if (largestIndex === currentIndex) break;

      this.swap(largestIndex, currentIndex);
      currentIndex = largestIndex;
    }

    return maxV;
  }
}

풀이

• 최대 힙을 통해 solution 구하기