[Javascript] 프로그래머스 - 디펜스 게임

문제 설명

준호는 병사 n명을 가지고 연속되는 적의 공격을 막아야 합니다. 각 라운드에서는 enemy[i]명의 적이 등장하며, 남은 병사 중 해당 수만큼 소모하여 적을 막을 수 있습니다.
병사의 수보다 많은 적이 등장하면 게임이 종료됩니다.
또한, k번의 무적권을 사용하여 병사를 소모하지 않고 한 라운드의 공격을 막을 수 있습니다.
무적권을 적절히 사용하여 최대한 많은 라운드를 막는 것이 목표입니다.

---

제한 사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• 모든 라운드를 막을 수 있다면 enemy.length를 반환

---

해결 방법

알고리즘: 우선순위 큐(최대 힙) 활용

1. 각 라운드마다 등장하는 적의 수를 sum 변수에 누적하여 병사가 부족한지를 확인합니다.
2. PriorityQueue(최대 힙)를 사용하여 현재까지 등장한 적 중 가장 많은 적을 저장합니다.
3. 누적된 적의 수가 n을 초과하면, k번까지는 가장 큰 적의 수를 제거하여 무적권을 사용한 효과를 냅니다.
4. 위 과정을 반복하며 최대한 많은 라운드를 버틸 수 있도록 합니다.

---

시간 복잡도

• 매 라운드마다 적을 PriorityQueue에 삽입 (O(log N))
• PriorityQueue에서 가장 큰 값을 제거하는 연산 (O(log N))
• enemy 배열의 길이를 M이라 할 때, 최악의 경우 O(M log M)

---

구현 코드

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

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

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

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return max;
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    let length = this.heap.length;

    while (true) {
      let leftChild = 2 * index + 1;
      let rightChild = 2 * index + 2;
      let largest = index;

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

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

      if (largest === index) break;
      this.swap(index, largest);
      index = largest;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

class PriorityQueue {
  constructor() {
    this.maxHeap = new MaxHeap();
  }

  enqueue(value) {
    this.maxHeap.push(value);
  }

  dequeue() {
    return this.maxHeap.pop();
  }

  isEmpty() {
    return this.maxHeap.isEmpty();
  }
}

function solution(n, k, enemy) {
  let answer = 0;
  const pq = new PriorityQueue();
  let sum = 0;

  for (let i = 0; i < enemy.length; ++i) {
    sum += enemy[i];
    pq.enqueue(enemy[i]);

    if (sum > n) {
      if (k <= 0) break;

      sum -= pq.dequeue();
      --k;
    }

    ++answer;
  }

  return answer;
}