[프로그래머스] 디펜스 게임 - Java (우선순위 큐)

프로그래머스

문제 설명

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

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

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

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

---

 

 

나의 풀이 - 1차 실패 (시간 초과, 런타임 에러)

문제를 보자마자 DFS로 무적권을 사용한 경우와, 사용하지 않은 경우를 같이 돌려서 해결해야 겠다는 생각이 들었습니다. 그래서 아래와 같이 코드를 작성했지만 오류가 발생했기에 다른 방식을 찾아야 했습니다.

class Solution {
    
    int finalRound = 0;
    int clearRound = 0;
    
    public int solution(int n, int k, int[] enemy) {
        finalRound = enemy.length;
        
        dfs(k, 0, n, enemy);
    
        return clearRound;
    }
    
    void dfs(int passCard, int round, int soldier, int[] enemy) {
        if (soldier < 0) {
            clearRound = Math.max(clearRound, round - 1);
            return;
        }
        
        if (round == finalRound) {
            clearRound = finalRound;
            return;
        }
        
        if (passCard != 0) {
            dfs(passCard - 1, round + 1, soldier, enemy);
        }
        dfs(passCard, round + 1, soldier - enemy[round], enemy);
    }
}

 

 

나의 풀이 - 2차 성공

라운드는 무조건 한번은 진행해야 합니다. 그렇기 때문에 라운드만 한 번식, 진행하면서 문제를 해결할 수 있는 방법을 생각해 보고자 했습니다.

무적권은 상대 enemy가 많은 라운드에 사용하는 것이 좋을 것 같습니다. 그렇기에 라운드를 진행하면서 우선순위 큐에 넣고 남은 병사가 없을 때 무적권을 사용하는 방식으로 진행해 봤습니다.

import java.util.*;

class Solution {

    public int solution(int n, int k, int[] enemy) {
        
        int soldier = n;
        int passCard = k;
        
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        
        int roundIndex = 1;
        for (int round : enemy) {
            queue.add(round);
            soldier -= round;
            
            if (soldier < 0) {
                while (!queue.isEmpty()) {
                    if (passCard == 0) {
                        break;
                    }

                    soldier += queue.poll();
                    passCard--;
                    
                    if (soldier >= 0) {
                        break;
                    }
                }
            }
            
            if (soldier < 0) {
                return roundIndex - 1;
            }
            
            roundIndex++;
        }
            
        return enemy.length;
    }
}