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

     

목차

 

 

문제

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

프로그래머스

 

 

 

문제 구현 방향

가능하다면 병력을 줄이고 힙에 저장해 놓는 식으로 진행을 하다가 불가능할 경우 힙에서 가장 큰 값을 꺼내 진행을 하는 식으로 설계하였다. 방향은 맞았으나 이전의 값들에서만 비교하여 무적권을 써서 틀린 문제였다. 현재의 값도 비교하여 무적권을 써줘야 한다.

 

 

 

코드 구현

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

  insert(val) {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 1 && this.heap[Math.floor(i / 2)] < this.heap[i]) {
      [this.heap[i], this.heap[Math.floor(i / 2)]] = [
        this.heap[Math.floor(i / 2)],
        this.heap[i],
      ];
      i = Math.floor(i / 2);
    }
  }

  remove() {
    if (this.heap.length === 1) return null;
    const max = this.heap[1];
    this.heap[1] = this.heap[this.heap.length - 1];
    this.heap.pop();
    let i = 1;
    while (true) {
      let left = i * 2;
      let right = i * 2 + 1;
      let largest = i;
      if (this.heap[left] && this.heap[left] > this.heap[largest]) largest = left;
      if (this.heap[right] && this.heap[right] > this.heap[largest]) largest = right;
      if (largest === i) break;
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      i = largest;
    }
    return max;
  }
}

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

  for (let i = 0; i < enemy.length; i++) {
    n -= enemy[i];
    heap.insert(enemy[i]);

    if (n < 0) {
      if (k > 0) {
        n += heap.remove();
        k--;
      } else {
        return i; // 더 이상 버티지 못함
      }
    }
  }
  return enemy.length;
}