Level 2) 디펜스 게임 ⭐️

Doozuu·2023년 6월 16일

프로그래머스 (JS)

목록 보기

116/183

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy의 길이 ≤ 1,000,000
1 ≤ enemy[i] ≤ 1,000,000
enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

입출력 예

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

아이디어

무적권을 적절한 시기에 사용하는 것이 문제의 포인트인데, 이 적절한 시기가 의미하는 바가 무엇일지 생각해보았다.

병사의 수를 최대한 적게 쓰려면 적의 수가 가장 많을 때 무적권을 사용하는 것이 가장 적절할 것이다.

근데 가장 많을 때의 기준이 언제인지 어떻게 판단할 수 있을까..? 사람이야 한눈에 봤을 때 적당히 이때 쓰면 되겠네~ 할 수 있지만 이걸 코드로 어떻게 짤 수 있을까..

현 지식으로는 생각하는데 한계가 있어서 방법을 찾아보았다.

찾아보니 힙이나 이분탐색을 이용해 풀어야 한다고 한다.

힙을 이용한 풀이는 이해가 어려워 이분탐색을 이용한 풀이를 분석해보았다.
이분탐색 풀이의 시간복잡도는 O(nlogn)이라고 한다.

처음에는 시작을 0으로, 끝을 enemy길이로 설정해둔다.
시작점이 끝점을 넘기 전까지 반복문을 시행한다.
시작점과 끝점의 가운데를 mid로 잡고, 0부터 mid까지 slice해서 내림차순으로 정렬한다.
배열에서 가장 큰 k개를 무적권으로 없애면 누적합을 최소한으로 만들 수 있으므로 k부터 끝까지 누적합을 구해준다.
변수(next)를 이용해 누적합이 n보다 작은지 저장한다.
- 누적합이 n보다 작다면 answer를 mid로 설정하고 start를 mid보다 한 칸 뒤로 옮긴다.(누적합을 늘리기 위함.)
- 누적합이 n보다 크다면 end를 mid보다 한 칸 앞으로 옮긴다.(누적합을 줄이기 위함.)
최적의 지점을 찾기 위해 start와 end를 조정하다가 start가 end보다 커지면 answer를 return한다.

예시

n = 7, k = 3, enemy = [4, 2, 4, 5, 3, 3, 1], answer = 5

첫 번째 시행
start = 0, end = 7, mid = 3
arr = [4,4,2]
temp = 0 (무적권이 3개이므로 무적권을 다써서 누적합 0임) -> n > temp
next = true
answer = 3, start = 4

두 번째 시행
start = 4, end = 7, mid = 5
arr = [5,4,4,3,2]
temp = 5 (무적권 3개를 써서 3 + 2가 누적합임) -> n > temp
next = true
answer = 5, start = 6

세 번째 시행
start = 6, end = 7, mid = 6
arr = [5,4,4,3,3,2]
temp = 8 (n보다 커져서 병사가 모자르다)-> n < temp
next = false
end = 5

=> 시작 지점이 끝 지점보다 커졌으므로(start(6) > end(5)) 반복문이 종료되고 answer로 저장되어 있는 5가 답이된다.

풀이

function solution(n, k, enemy) {
    let answer = 0;
    let start = 0; 
    let end = enemy.length;
    
    while(start<=end){
        let mid = Math.floor((start+end)/2);
        let arr = enemy.slice(0, mid).sort((a, b)=> b-a);
        
        let next = true;
        let temp = 0;
        for(let i=k ; i<arr.length; i++){
            temp += arr[i];
            if(temp > n) next = false;
        }
        
        if(next) {
            answer = mid;
            start = mid+1;
        }
        else end = mid-1;
    }
    
    return answer;
}