[프로그래머스] 디펜스 게임 - Javascript

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/142085#

프로그래머스

 

 

문제 요약 :

1. 라운드 별로 enemy[i] 명의 적이 등장한다.
2. 아군 병사 n명과 라운드 스킵 횟수 k를 이용하여 최대 클리어 가능 라운드 수를 출력하라

 

문제 풀이 시간 : 30분

문제 성공 여부 : 성공

 

접근 방법(성공) :

1. 이진탐색으로 최대 클리어 가능한 라운드 수 구하기

 

내가 생각한 문제의 핵심은 다음과 같다.

 

1. 무적권(k)는 특정 범위(라운드)에서 가장 큰 수부터 사용해야한다.

2. 가장 큰 수를 구하는 쉬운 방법은 힙을 사용하거나 정렬을 하는 것이다.

 

자바스크립트에서 힙을 구현하는 것은 클래스를 하나 구현해야 하는 것이기 때문에 가장 먼저 정렬방식을 고민해 보았다.

 

0~t까지의 범위가 가능한지 파악하기 위해서는 다음과 같은 과정이 필요하다.

1. 0~t 배열을 내림차순 정렬

2. 배열[k]부터 끝까지의 합을 구한다.(0~k까지는 무적권을 사용하기 때문)

3. n과 비교하여 배열의 합이 더 클 경우 디펜스 가능여부를 파악 가능하다.

 

enemy는 최대 100만이기에 정렬 시간복잡도는 크지 않다.

 

하지만, 0~enemy.length까지 모든 범위에 대해서 정렬을 하며 합을 구하는 것은 사실상 O(len^2)까지 도달하니,

이진탐색을 활용해 보았다.

 

 

left~mid까지 배열을 잘라 내림차순 정렬을 하여, n개보다 큰지 작은지 비교를 수행하여 이진 탐색 범위를 좁혀간다

 

이진탐색은 최대 log(len)만 수행하면 범위를 알 수 있기 때문에 log(len)만큼만 정렬을 수행하면 된다.

 

문제는, 배열[k]부터 끝까지의 합을 구할 때 최악의 경우 O(len)만큼의 연산이 이루어지기 때문에 살짝 위험할 수 있다고 판단하였지만, 시간 초과가 날 경우 누적합을 넣으면 충분히 해결될 수 있을 것 같아 코드를 짜보았다.

 

 

 

 

전체 코드(성공) :

function solution(n, k, enemy) {
    if(k >= enemy.length) return enemy.length;
    let left = 0;
    let right = enemy.length-1;
    let ans = 0;
    
    while(left<=right){
        let mid = Math.floor((left+right)/2);
        const arr = getDeOrderedArr(enemy,mid);
        const enemyCnt = getEnemyCnt(arr,k);
        
        if(enemyCnt<=n){ // 막을 수 있으면 최대 라운드 수를 늘려본다
            left = mid+1;
            ans = left; 
        }
        else{
            right = mid-1;            
        }
    }
    
    return ans;
}

// 0~k를 제외한 적의 수
const getEnemyCnt = (arr,k) => {
    let enemyCnt = 0;
    for(let i=k; i<arr.length; i++){
        enemyCnt += arr[i];
    }
    return enemyCnt;
}

// 0~end 까지의 배열을 내림차순 정렬
const getDeOrderedArr = (arr, end) => {
    const newArr = arr.slice(0,end+1);
    newArr.sort((a,b)=>b-a);
    return newArr;
}

 

살짝 아슬하게 정답이 나왔다!

 

힙을 쓰면 훨씬 빠르게 풀이가 가능할 것 같다