문제

풀이 과정

요약

Map 을 사용하는 문제.

상세

1. 먼저 무적권의 갯수인 $k$ 보다 게임의 총 횟수가 적다면, 무적권만 사용해도 게임을 클리어할 수 있으므로 이때는 게임의 횟수를 반환해주자.
2. 이분 탐색을 활용하여,해당 라운드 까지 디펜스 할 수 있는지 탐색한다. 검증과정은 다음과 같다.

• $enemy$ 데이터를 기반으로, 임의의 라운드까지 배열을 복사한다. 복사한 배열을 내림차순으로 정렬한다.
• 현재의 총 누적값을 구한다. 단 무적권이 아직 존재한다면, 무적권을 소모하여 구한다. 무적권은 현재 라운드까지 적이 가장 많이 몰려오는 곳에서 사용하기 위해서, 내림차순으로 정렬한 것이다. 무적권을 사용할 때에는 해당 라운드의 수는 누적값에 반영되지 않는다.
• 그렇게 나온 값을 $n$ 과 비교한다. $n$ 이 동일하거나 더 크면 현재 라운드까지 버틸 수 있다는 것이다.

3. 참이 나오면, 이전 라운드까지 모두 버틸 수 있는 것이므로, $l$ 값을 높여주고, 아니라면 그 이후 라운드는 모두 버틸 수 없으므로, $r$ 값을 낮춰주자.

정답

function solution(n, k, enemy) {
  if (k >= enemy.length) return enemy.length;
  let l = 0;
  let r = enemy.length;

  function check(pos) {
    let temp = enemy.slice(0, pos).sort((a, b) => b - a);
    let tk = k;
    let sum = temp.reduce((acc, cur) => {
      if (tk > 0) {
        tk--;
        return acc;
      }
      return acc + cur;
    }, 0);
    return sum <= n;
  }

  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (check(mid)) l = mid + 1;
    else r = mid - 1;
  }
  return r;
}