디펜스 게임 (Programmers Lv.2)

 

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

https://school.programmers.co.kr/learn/courses/30/lessons/142085?language=cpp

 

먼저 언제나처럼 C++로 도전했다...!

처음에는 dp로 접근했는데 시간초과가 발생해서 재귀로 시도했지만 다시 실패...
priority_queue를 이용하는 문제 풀이는 특별히 기억할 만 해서 복습하는 시간을 따로 가졌다.

 

C++ 풀이)

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = enemy.size();
    priority_queue<int, vector<int>, less<int>> pq;
    
    for(int i = 0; i < enemy.size(); i++) {
        pq.push(enemy[i]);
        n -= enemy[i];
        
        if(n < 0) {
            if(k == 0) {
                answer = i;
                break;
            }
            
            // 무적권
            while(!pq.empty() && k > 0 && n < 0){
                k--;
                n += pq.top();
                pq.pop();
            }
        }
    }
    
    return answer;
}

 

하지만 이도 문제가 있었는데, 해당 로직을 Javascript로 변환하면 시간 초과가 발생한다...!

그래서 한 문제이지만 두 가지 문제 풀이를 생각할 수 밖에 없었다.

다행인지 불행인지, 이번에는 JS로 문제를 풀 수 있었다!!! (아마 c++로 못 푼 문제 js로 푼 거 처음인 듯...?)

 

과감하게 코드를 지워버리고 이분탐색을 수행!

어자피 enemy 배열 크기 내에서 값이 정해지기에 시도해봤는데, 성공해버렸단 말씀!

 

JS 풀이)

function solution(n, k, enemy) {
    let answer = enemy.length;
    
    let low = 0, high = enemy.length;
    while(low <= high) {
        let mid = Math.floor((low + high) / 2);
        let curEnemy = enemy.slice(0, mid).sort((a, b) => b - a);
        let curK = k;
        
        const curSum = curEnemy.reduce((acc, val) => {
            if (curK > 0) {
                curK--;
                return acc;
            }
            else
                return acc + val
        }, 0);
        
        if(n - curSum >= 0)
            low = mid + 1;
        else
            high = mid - 1;
    }
    
    answer = low - 1;
    
    return answer;
}

 

뭐 다른 깔끔한 풀이가 많은 것 같다. 하지만 이번에는 내가 짠 알고리즘을 되짚는 게 더 나은 듯 싶어 이렇게 가져와보았다! 매일 알고리즘을 풀고 있지만, 요즘 따라 효율이 좋지 않은 것 같다... 조금 더 집중해서 공부하자!!!