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

디펜스 게임

문제 링크

디펜스 게임

분석

각 라운드마다 enemy[i]만큼의 적이 등장합니다.
해당 라운드에 남은 병사 수가 라운드의 병사 수보다 많다면 라운드의 병사 수만큼 소모하여 막을 수 있습니다.
만약 막을 수 없는 경우 라운드가 종료됩니다.

무적권이라는게 존재하는데, 이 무적권을 사용하면 병사의 소모 없이 라운드의 enemy[i]을 막을 수 있습니다.

이때, 최대로 버틸 수 있는 라운드 수를 구하고, 반환해야합니다.

n은 가지고있는 병사의 수를 의미합니다.
k는 가지고있는 무적권의 수를 의미합니다.
enemy는 적의 수가 순서대로 담긴 정수 배열입니다.

무적권을 사용한다면, 가장 병사가 많이 드는 라운드에서 사용해야합니다.
하지만, 게임 규칙과 별개로 결과만 구하면 되기 때문에 병사를 모두 소모하고 게임이 끝났을 때 무적권을 사용하면 됩니다.
지나온 라운드 중에서 가장 병사가 많이 소모된 구간에 무적권을 사용하고 병사의 수를 복구하면 됩니다.
그 후, 다시 라운드를 진행하며 라운드가 끝날 때마다 무적권을 사용하고, 다 사용했을 경우 종료되면 됩니다.

지나온 라운드 중 가장 병사가 많이 소모된 값은 우선순위 큐로 최대 힙에 저장하면 효율적입니다.

풀이

#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    // 우선순위 큐(최대힙)으로 지금까지 각 라운드에서 소모된 병사의 값을 저장
    priority_queue<int> maxHeap;
    
    // 라운드 진행
    for (int i = 0; i < enemy.size(); ++i)
    {
        // 일단 가지고있는 병사로 적을 막고, 가진 병사 수 차감
        n -= enemy[i];
        // 해당 라운드에서 소모된 병사의 값을 저장
        maxHeap.push(enemy[i]);
        
        // 가지고있는 병사가 부족한 경우
        if (n < 0)
        {
            // 무적권이 남아있는 경우
            if (k > 0)
            {
                // 무적권을 사용하고 가장 많이 소모된 병력을 회수한다.
                int biggest = maxHeap.top();
                maxHeap.pop();
                
                n += biggest;
                --k;
            }
            else
            {
                // 무적권이 없고, 병사가 부족한 경우이므로 현재 라운드에서 종료
                return i;
            }
        }
    }
    
    // 모든 라운드를 통과한 경우
    return enemy.size();
}

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 라운드를 진행하는 반복문 $O(n)$
• 반복문 안에서 우선순위 큐의 삽입, 삭제 $O(log \ k) \approx $O(log \ n)$
  • k는 우선순위 큐에 삽입된 요소 수로, 최대 n개가 삽입 될 수 있다.
• $O(n) \times O(log \ n)$

공간 복잡도는 $O(n)$입니다.

• 각 라운드에서 소모된 병사의 값을 저장하는 priority_queue<int> maxHeap $O(n)$

테스트 성능

테스트 1 〉 통과 (0.10ms, 4.21MB)
테스트 2 〉 통과 (0.47ms, 6.59MB)
테스트 3 〉 통과 (19.67ms, 38.3MB)
테스트 4 〉 통과 (3.17ms, 34.7MB)
테스트 5 〉 통과 (0.27ms, 4.21MB)
테스트 6 〉 통과 (24.42ms, 38.6MB)
테스트 7 〉 통과 (8.37ms, 37.7MB)
테스트 8 〉 통과 (7.02ms, 37.6MB)
테스트 9 〉 통과 (7.26ms, 37.5MB)
테스트 10 〉 통과 (19.72ms, 40.5MB)
테스트 11 〉 통과 (2.69ms, 34.7MB)
테스트 12 〉 통과 (2.45ms, 34.7MB)
테스트 13 〉 통과 (0.01ms, 4.05MB)
테스트 14 〉 통과 (0.01ms, 4.22MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.2MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 4.14MB)
테스트 19 〉 통과 (0.01ms, 4.16MB)
테스트 20 〉 통과 (0.01ms, 3.67MB)
테스트 21 〉 통과 (0.03ms, 4.05MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 4.14MB)
테스트 24 〉 통과 (0.01ms, 4.2MB)
테스트 25 〉 통과 (0.01ms, 3.68MB)
테스트 26 〉 통과 (0.01ms, 3.59MB)
테스트 27 〉 통과 (0.01ms, 4.21MB)
테스트 28 〉 통과 (0.01ms, 4.45MB)
테스트 29 〉 통과 (0.02ms, 4.14MB)
테스트 30 〉 통과 (0.01ms, 4.22MB)
테스트 31 〉 통과 (0.01ms, 4.16MB)
테스트 32 〉 통과 (0.01ms, 4.21MB)