[programmers/py] 디펜스 게임

디펜스 게임

https://school.programmers.co.kr/learn/courses/30/lessons/142085

문제 설명

• 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다.
• 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.

문제 풀이

1. 큐 사용
   병사 수 > 내 병사면 무적권 사용

from heapq import heappush, heappop

def solution(n, k, enemy):
    h = []
    answer, e_sum = 0, 0
    
    for e in enemy:
        heappush(h, -e)
        e_sum += e
        
        if e_sum > n:
            if k == 0: break
            e_sum += heappop(h)
            k -= 1
        answer += 1
    
    return answer

2. 이분 탐색

function solution(n, k, enemy) {
    // n은 병사, k는 무적권, enemy는 리스트
    let left = 0;
    let right = enemy.length;
    
    while (left <= right) {
        const mid = Math.trunc((left + right) / 2);
        const dieEnemy = enemy.slice(0, mid).sort((a,b) => b - a);
        let chance = k;
        
        const sumEnemy = dieEnemy.reduce((a, c) => {
            // 무적권이 있다면
            if(chance > 0) {
                chance -= 1;
                return a;
            }
            return a + c;
        }, 0)
        
        // 병사 또는 무적권이 남으면 left 증가
        if(n - sumEnemy >= 0 && chance >= 0) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return left - 1;
}