프로그래머스 디펜스 게임 JavaScript

2023년 1월 12일

프로그래머스 디펜스 게임

문제 풀이

오랜만에 푼 이분 탐색 문제였다. n명의 병사를 소모하여 라운드마다 enemy[i] 명의 적을 막을 때 최대한 많은 라운드를 진행하는 것이 목적, 이 때 무적권이라는 스킬을 사용하면 병사의 소모 없이 한 라운드의 공격을 막을 수 있다.

enemy의 길이가 최대 1,000,000이기에 이분 탐색을 통해 가능한 최대 라운드를 탐색한다.

function roundCheck(n, k, range, enemy):

rangeEnemy: 인덱스 0부터 range 전까지 enemy를 slice()와 내림차순으로 sort()한 리스트
solider: 남은 병사의 수
cnt: 남은 무적권 수
내림차순으로 정렬했기에 무적권이 남아있으면 사용하고, 없을 경우에 병사 수가 적보다 작을 시에 false를 리턴,
rangeEnemy를 전부 통과하면 range까지의 라운드를 통과할 수 있음 => true 리턴

true가 리턴되면 이전 까지의 라운드는 다 통과할 수 있으므로 left = mid + 1
false가 리턴되면 해당 라운드(mid)는 통과할 수 없으므로 right = mid - 1

solution.js

function solution(n, k, enemy) {
    let left = 0;
    let right = enemy.length;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        roundCheck(n, k, mid, enemy) === true ? left = mid+1 : right = mid-1;
    }
    return left-1;
}

function roundCheck(n, k, range, enemy) {
    const rangeEnemy = enemy.slice(0, range).sort((a, b) => b-a);
    let solider = n;
    let cnt = k;
    for (let i = 0; i < rangeEnemy.length; i++) {
        if (cnt > 0) {
            cnt -=1;
        }
        else {
            if (solider - rangeEnemy[i] < 0) {
                return false;
            }
            solider -= rangeEnemy[i];
        }
    }
    return true;
}

프로그래머스 디펜스 게임 JavaScript

문제 풀이

댓글