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

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

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

 

문제 풀이

 저는 처음 이 문제에 접근할 때 무적권 사용 유무에 따라 처리해야 한다고 생각했고 완전탐색보다는 dp를 통해 각 라운드별로 무적권 사용횟수를 기준으로 dp를 적용해나가면 답이 나올 것이라 생각하고 접근했습니다.

<1번 째 접근 방식>

공간복잡도를 생각하지않고 구현해보자는 생각으로 2차원 배열로 접근했고 테스트케이스는 통과했지만 메모리초과를 겪었습니다.  (71.9점)

class Solution {
    private int[][] dp;
    
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        dp = new int[k+2][enemy.length+1];
        dp[1][0] = n;
        
        for (int i=1; i<=enemy.length; i++) {
            for (int j=1; j<=k+1; j++) {
                dp[j][i] = Math.max(
                    dp[j][i-1] - enemy[i-1] > 0 ? dp[j][i-1] - enemy[i-1] : 0,
                    dp[j-1][i-1]
                );
            }
            
            if (i == enemy.length) continue;
            if (i < k) continue;
            
            boolean gameOver = true;
            for (int j=1; j<=k+1; j++) {
                if (dp[j][i] >= enemy[i]) {
                    gameOver = false;
                    break;
                }
            }
            
            if (gameOver) {
                return i;
            }
        }
        
        return enemy.length;
    }
}

/* 라운드 1 2 3 4 5 6 7
*      0 0 0 0 0 0 0
*      7 3 1 0 0 0 0
*      0 7 5 1 0 0 0
*      0 0 7 5 1 0 0 
*      0 0 0 7 5 2 0
*/

 

<2번 째 접근 방식>

2번 째에는 2차원 배열로 이뤄진 dp를 1차원 배열로 변경하여 메모리 초과를 해결하였지만 이것 역시 k*ememy의 길이가 최악으로 잡아야하기에 시간초과가 났습니다 (84.4점)

class Solution {
    private int[] dp;
    
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        dp = new int[k+2];
        dp[1] = n;
        
        for (int i=0; i<enemy.length; i++) {
            int[] temp = new int[k+2];
            
            for (int j=1; j<=k+1; j++) {
                temp[j] = Math.max(
                    dp[j] - enemy[i] > 0 ? dp[j] - enemy[i] : 0,
                    dp[j-1]
                );
            }
            
            for (int j = 0; j <= k+1; j++) {
                dp[j] = temp[j];
            }
            
            if (i == enemy.length-1) continue;
            if (i < k-1) continue;
            
            boolean gameOver = true;
            for (int j=1; j<=k+1; j++) {
                if (dp[j] >= enemy[i+1]) {
                    gameOver = false;
                    break;
                }
            }
            
            if (gameOver) {
                return i+1;
            }
        }
        
        return enemy.length;
    }
}


/* 라운드 1 2 3 4 5 6 7
*      0 0 0 0 0 0 0
*      7 3 1 0 0 0 0
*      0 7 5 1 0 0 0
*      0 0 7 5 1 0 0 
*      0 0 0 7 5 2 0

* -> 0 7 0 0 0
* -> 0 3 7 0 0
* -> 0 1 5 7 0
* -> 0 0 1 5 7
* -> 0 0 0 0 2
*/

 

<정답>

따라서 생각을 달리하여 우선순위 큐로 접근했더니 쉽게 해결할 수 있었습니다.

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int round = 0; round < enemy.length; round ++) {
            queue.add(enemy[round]);
            
            if (queue.size() > k)
                n -= queue.poll();
            
            if (n < 0)
                return round;
        }
        return enemy.length;
    }
}

 

<출처>

프로그래머스