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

문제

디펜스 게임

https://school.programmers.co.kr/learn/courses/30/lessons/142085

 

 

예시 코드

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

  push(v) {
    this.heap.push(v);
    this.heapUp();
  }

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

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

    return v;
  }

  heapUp() {
    let child = this.size() - 1;
    let parent = this.getParent(child);

    while (this.heap[child] > this.heap[parent]) {
      this.swap(child, parent);
      child = parent;
      parent = this.getParent(child);
    }
  }

  heapDown() {
    let parent = 0;

    while (true) {
      const left = this.getLeftChild(parent);
      const right = this.getRightChild(parent);
      let biggest = parent;

      if (left < this.size() && this.heap[biggest] < this.heap[left])
        biggest = left;
      if (right < this.size() && this.heap[biggest] < this.heap[right])
        biggest = right;

      if (biggest === parent) break;

      this.swap(parent, biggest);
      parent = biggest;
    }
  }

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

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  getParent(child) {
    return Math.floor((child - 1) / 2);
  }
  getLeftChild(parent) {
    return parent * 2 + 1;
  }
  getRightChild(parent) {
    return parent * 2 + 2;
  }
}

function solution(n, k, enemy) {
  const heap = new MaxHeap();

  for (let i = 0; i < enemy.length; i++) {
    const enemyCnt = enemy[i];
    n -= enemyCnt;
    heap.push(enemyCnt);
    if (n >= 0) continue;
    if (k === 0) return i;
    const maxEnemyCnt = heap.pop();
    n += maxEnemyCnt;
    k--;
  }

  return enemy.length;
}

 

 

풀이

최대 몇 라운드까지 온전히 방어할 수 있는지를 구하는 문제입니다.

무적권은 실제로 진행된 라운드 중 적의 수가 가장 많을 때 사용해야 합니다.

이를 위해서 최대 힙을 사용합니다.

 

라운드를 진행하며 적의 수를 최대 힙에 집어넣고, 그만큼 병사 수를 감소시킵니다.

만약 남은 병사 수가 0보다 작아지면, 무적권이 남아있는지 확인합니다.

무적권이 남지 않은 경우, 더 이상 라운드를 진행할 수 없으므로, 마지막으로 막은 라운드 번호를 반환합니다.

무적권이 남은 경우, 최대 힙에서 pop을 합니다. 이 값은 지금까지 라운드를 진행하며 만났던 가장 많은 적의 수입니다. 해당 값만큼 병사 수를 회복하고, 무적권을 차감합니다.

 

모든 라운드를 방어해냈다면 마지막 라운드 번호를 반환합니다.