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

🧡문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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

---

💙입출력 예 설명

입출력 예#1

• 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.

입출력 예#2

• 준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.

---

💜나의 풀이

처음 나의 풀이는 이러한 느낌이였다

효율성 문제도 그렇고 풀이 자체가 잘못되었다는걸 깨닫고 참고할만한 문서를 찾기 시작했음

function solution(n, k, enemy) {
    let result = 0
    const sortedEnemy = enemy.sort((a,b) => b-a).slice(0,k).sort((a,b) => a-b)
    for(let i = 0 ; i < enemy.length ; i ++) {
        // 무적권을 사용해야하는 경우라면
        const useNoDie = sortedEnemy.indexOf(enemy[i])
        if(useNoDie > -1) {
            sortedEnemy.splice(useNoDie,1)
            k--
        // 이번 병사를 막을 수 있는 병력이나 무적권이 있다면
        } else if(n >= enemy[i]) {
            n-=enemy[i]
        } else if(k > 0) {
            k--
        } else {
            break
        }
        result++
    }
    // 모든 라운드를 막을 수 있다면
    if(result === enemy.length) {
        return enemy.length
    }
    return result
}

이 문제는 이분탐색으로 해결해야한다. 아니면 큐를 사용한 작업을 해야하는데 난 이분탐색풀이법이 조금 더 맞는 것 같음

function solution(n, k, enemy) {
    // 이분 탐색을 진행하기 위한 left, mid, right 변수 선언
    let [left, right] = [0, enemy.length]
    let mid = Math.floor((left+right)/2)
    while(left <= right) {
        // 해당 탐색에서 사용될 길이 내림차 순(k 소진을 위함)
        const curSlice = enemy.slice(0, mid).sort((a,b) => b-a)
        let noDie = k
        // 전쟁 후 남을 상대 병사의 수
        const curEnemy = curSlice.reduce((acc, cur) => {
            // 무적권이 있다면
            if(noDie > 0) {
                noDie--
                return acc
            }
            return acc+cur
        }, 0)
        // 상대 병사를 무적권 한도 내에 모두 무찌를 수 있는가?
        if(n-curEnemy >= 0 && noDie >= 0) {
            left = mid + 1
        } else {
            right = mid - 1
        }
        mid = Math.floor((left+right)/2)
    }
    return left-1
}