디펜스 게임

내 할일 잘 하기·2023년 3월 8일

코딩테스트 프로그래머스

Programers :: Level 2

목록 보기

4/7

💡

문제 설명

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

나의 생각

무적권은 언제나 enemy[i]가 가장 클 때 ( = i가 가장 클 때 ) 사용해야 함.

reduce를 사용해보자.

무적권으로 막을 수 있는 적의 수를 count 해야할 것 같은데.

function solution(n, k, enemy) {
    let free = [];
    let freeCount = 0;
    let round = 0;
    var answer = enemy.reduce((acc,curr,idx,arr)=>{
// 무적권 처리
        if(free.length === k){
            const min = Math.min(...free);
            if (curr>min) {
                freeCount += (curr-min);
                free[free.indexOf(min)] = curr;
            }
        } else {
            freeCount += curr;
            free.push(curr)
        }
        
// Answer 처리
        if(n<(acc + curr - freeCount)) {
            round = idx;
            arr.splice(1);
        }else {
            round++
            return  acc+curr;   
        }
    },0)
    return round
}

⇒

정확성: 90.6
합계: 90.6 / 100.0

음.. enemy 들어오는 데이터를 heap으로 구현하는 방식으로 해볼까..?

각 라운드별 최대값을 가진 node를 찾아야 하기 때문에, 완전 이진트리인 힙을 사용하는게 맞는 것 같은데..

maxHeap 으로, 각 라운드 enemy input → 무적권 사용 ( 최대값 node 값 무효화 ) → 성공 여부 확인 → (성공시) 다음 라운드 진행 / (실패시) 종료 및 결과값 리턴..

이런 방식인가?

아니지...

결국 원하는 답은, 몇 라운드나 버틸 수 있는지? 인데..?
그걸 위한 코드를 이진 탐색으로 짜보자.

성공/실패를 return하는 함수 생성 → [left = 성공,current,right = 실패] ?로 이진탐색 시키면 될 것 같다!!

그렇다면, 항상 단순히 절반으로 찾아가면 될까?
더 정확도가 높은 알고리즘을 찾을 수는 있겠지만,
이미 이분탐색으로 접근한 결과 더 좋은 알고리즘을 사용한다고 해도 탐색 횟수에 큰 차이는 없을 것으로 판단되니까 절반씩 쳐내는걸로 하자.

다만, 무적권을 감안하여 초기값을 잘 설정해보자.

나의 풀이

function solution(n, k, enemy) {
    // 무적권이 더 많은 경우 바로 끝내기
    if (k >= enemy.length) {
        return enemy.length;
    };
    // 특정 라운드의 result 및 index를 return하는 함수 선언. ( false는 성공, true는 실패 )
    const resultCheck = (index) => {
        return {index: index, result: enemy.slice(0,index).sort((a,b)=>b-a).slice(k).reduce((acc,curr)=>acc+curr) > n}
    };

    // 마지막 라운드 결과가 false(성공)일 경우, 바로 끝내기
    const maxCheck = resultCheck(enemy.length);
    if(!maxCheck.result){
        return enemy.length
    };

    // 무적권 소모 후 첫 라운드 결과가 true(실패)일 경우, 바로 끝내기
    const minCheck = resultCheck(k+1);
    if(minCheck.result){
        return k
    }
    // 값 초기화
    let check = [minCheck,
                 resultCheck(Math.floor((k + enemy.length)/2)),
                 maxCheck];
    while(check[0].index + 2 < check[2].index){
        console.log(check)
        if(check[1].result) {
            // 실패시
            check[2] = check[1];
        } else {
            // 성공시
            check[0] = check[1];
        }
        check[1] = resultCheck(Math.floor((check[0].index + check[2].index)/2));
    };
    console.log(check);
    return check[1].index - (check[1].result)
}