[프로그래머스] Lv2. 디펜스 게임- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 디펜스 게임

문제

제한사항

📌 내가 생각한 풀이

문제의 제한사항을 보면 숫자가 엄청 크다. 즉, 완전탐색으로 풀면 분명 시간복잡도가 초과가 될 것 이다. 여기서 이분탐색을 사용하자.

0부터 ~ (l~r)/2 까지의 자른 slice는 무조건 클리어 할 수 있다고 가정하고, 만약 n이 더 남는다면 l을 키우고, n이 부족하다면 1을 감소시켜서 while문을 돌자!

//dp를 이용해서 풀까?
//이분탐색으로 풀자!
// l~r범위에 있는 애들은 다 잡을 수 있다고 가정
// l~r범위 내림차순으로 sort, 무적권 먼저 사용
// 1트 : 65.0
// 2트 : 78.1
// 3트 : 84.4
// 4트 : 100,0

function solution(n, k, enemy) {
    var answer = 0;

    let [l,r] = [0, enemy.length];
    let mid = 0;
    while(l<=r){
        mid = Math.floor((l+r)/2);
        let slice = enemy.slice(0,mid);
        slice.sort((a,b)=>b-a);
        let sum = 0;
        let idx = k;
        for(var j = k; j<slice.length; j++){
            sum+=slice[j];
        }
        if(sum <= n){
            l = mid+1;
        }else{
            r = mid-1;
        }   
    }
    return l-1;
    
    
}

📌 느낀점

시간복잡도면에서 해결하기 조금 어려운 문제였다. 이분탐색을 별로 써보지 않아서, 어색했지만, 맞춘다음, 다시 풀면서 완벽하게 이해했다. 카카오 문제 중 징검다리 건너기 문제가 이분탐색을 이용하여 푸는 문제이므로, 풀어보는것도 추천한다.