Portfolio

풀이

재영

최소 힙을 만든다.

최소 힙을 만드는 건 → 일단 무적권을 쓰고 봐요.

다 썼잖아요 → 문제: 이것이 최선의 방법은 아니었을 것이라는 가정을 항상 해요.

바꿔주는 거에요 → 현재 적의수 vs 힙에 들어있는 최소 적의수


class MinHeap {
  constructor() {
    this.heap = [null];
    this.size = 0;
  }
  heappush(value) {
    this.heap.push(value);
    let nowIndex = this.heap.length - 1;
    let parentIndex = Math.floor(nowIndex / 2);
    while (nowIndex > 1 && this.heap[parentIndex] > this.heap[nowIndex]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = Math.floor(nowIndex / 2);
    }
    this.size += 1;
  }
  heappop() {
    if (this.size === 0) throw new Error;
      
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let nowIndex = 1;
    let leftIndex = nowIndex * 2;
    let rightIndex = nowIndex * 2 + 1;

    while (
      this.heap[nowIndex] > this.heap[leftIndex] ||
      this.heap[nowIndex] > this.heap[rightIndex]
    ) {
      if (this.heap[rightIndex] < this.heap[leftIndex]) {
        this.swap(nowIndex, rightIndex);
        nowIndex = rightIndex;
      } else {
        this.swap(nowIndex, leftIndex);
        nowIndex = leftIndex;
      }

      leftIndex = nowIndex * 2;
      rightIndex = nowIndex * 2 + 1;
    }

    this.size -= 1;
    return returnValue;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  get length() {
    return this.size;
  }

  get min() {
    return this.heap[1];
  }
}

function solution(n, k, enemy) {
  let result = 0;

  let nCount = n;
  let kCount = k;

  const powerOverWhelming = new MinHeap();
    
  enemy.forEach((e) => {
    if (nCount < 0) return;

    if (kCount) {
      kCount -= 1;
      powerOverWhelming.heappush(e);
    } else {
      if (powerOverWhelming.length) {
        if (powerOverWhelming.min < e) { 
          powerOverWhelming.heappush(e);
          nCount -= powerOverWhelming.heappop();
        } else {
          nCount -= e;
        }
          
        if (nCount < 0) return;
      }
    }
    
    result += 1;
  });

  return result;
}

효성


class MyHeap {
  constructor() {
    this.heap = []; 
  }
  size() {
    return this.heap.length;
  }
  push(node) {
    this.heap.push(node);
    let curIdx = this.heap.length - 1;
    let parentIdx = Math.floor((curIdx - 1) / 2);

    while (this.heap[parentIdx] < this.heap[curIdx]) {
      [this.heap[parentIdx], this.heap[curIdx]] = [
        this.heap[curIdx],
        this.heap[parentIdx],
      ];
      curIdx = parentIdx;
      parentIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  pop() {
    let lastIdx = this.heap.length - 1;
    let curIdx = 0;
    [this.heap[curIdx], this.heap[lastIdx]] = [
      this.heap[lastIdx],
      this.heap[curIdx],
    ];
    const result = this.heap.pop();
    lastIdx = this.heap.length - 1;

    while (curIdx < lastIdx) {
      let leftIdx = curIdx * 2 + 1;
      let rightIdx = curIdx * 2 + 2;
      if (this.heap[leftIdx] == null) break;
      if (this.heap[rightIdx] == null) {
        if (this.heap[curIdx] < this.heap[leftIdx]) {
          [this.heap[curIdx], this.heap[leftIdx]] = [
            this.heap[leftIdx],
            this.heap[curIdx],
          ];
        }
        curIdx = leftIdx;
        break;
      }

      if (
        this.heap[curIdx] < this.heap[leftIdx] ||
        this.heap[curIdx] < this.heap[rightIdx]
      ) {
        const maxIdx =
          this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
        [this.heap[curIdx], this.heap[maxIdx]] = [
          this.heap[maxIdx],
          this.heap[curIdx],
        ];
        curIdx = maxIdx;
      } else {
        break;
      }
    }
    return result;
  }
}

function solution(n, k, enemy) {
    const len = enemy.length;
    let answer = 0;

    if(len <= k) {
        return len;
    }
    
    const heap = new MyHeap();
    
    for(let i = 0; i < len; i++) {
        heap.push(enemy[i]);
        n -= enemy[i];
        
        if(n < 0) {
            if(k > 0) {
                const max = heap.pop();
                n += max;
                k -= 1;
            }
            else break;
        }
        
        answer += 1;
    }
    return answer;
}

디펜스 게임

풀이