[프로그래머스] 디펜스 게임 / JavaScript / Level 2

🚩문제 주소

📄풀이

이분탐색

1. left와 right를 정합니다.
2. left가 right이하 일 때까지
   • mid를 설정합니다.
   • enemy배열을 mid까지 slice를 해서 내림차순으로 정렬합니다. 내림차순으로 정렬을 하는 이유는 무적권을 적의 수가 많을 때 사용해야 이득이기 때문입니다.
   • 자른 enemy배열을 더해주어야 하는데 무적권이 남아있다면 무적권을 사용하고 적을 더하지 않습니다. 무적권을 모두 사용했다면 적을 더합니다.
   • 더한 적의 수를 n에서 빼도 0 이상이라면 left를 늘리고 아니라면 right를 줄입니다.
3. right를 반환합니다.

👨‍💻코드

function solution(n, k, enemy) {
  // 이분탐색
  let [left, right] = [0, enemy.length];

  while (left <= right) {
    let mid = parseInt((left + right) / 2);
    const enemy_cut = enemy.slice(0, mid).sort((a, b) => b - a);
    // mid까지 slice를 해서 내림차순으로 정렬 
    // -> 무적권을 적의 수가 많은 순으로 사용하기 위해서
    let copy_k = k;

    const enemy_sum = enemy_cut.reduce((acc, cur) => {
      // slice한 enemy를 더해주는데
      if (copy_k > 0) {
        // 무적권이 남아있다면 무적권을 사용
        copy_k--;
        return acc;
      }
      return acc + cur; // 무적권이 없다면 적의 수를 더함
    }, 0);

    if (n - enemy_sum >= 0) left = mid + 1;
    else right = mid - 1;
    // 남은 병사의 수에서 적의 수의 합을 뺀 수가 0 이상이라면 left를 늘리고
    // 아니라면 right를 늘린다.
  }
  return right;
}