디펜스 게임(Java)

bearMin·2024년 3월 24일

🎯문제

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

✏️풀이

코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = enemy.length, soldier = n, skill = k;
        // 우선순위 큐 생성
        // 내림차순으로 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i = 0; i < enemy.length; i++) {
            // 병사의 수에서 적의 수를 빼줌
            soldier -= enemy[i];
            // 해당 라운드의 적의 수를 저장
            pq.add(enemy[i]);
            
            // 병사의 수가 0보다 작을 경우
            if(soldier < 0) {
            	// 스킬이 있으면서 큐가 비어있지 않을 경우
                if(skill > 0 && !pq.isEmpty()) {
                	// 가장 많은 병사의 수를 가져옴
                    soldier += pq.poll();
                    // 스킬의 횟수를 감소
                    skill--;
                }
                // 스킬이 없거나 큐가 비어있을 경우
                else {
                	// 해당 라운드를 answer에 저장 후 break
                    answer = i;
                    break;
                }
            }
        }
        
        return answer;
    }
}

설명

우선순위 큐를 사용해서 진행하였다.

우선순위 큐를 생성하는데 이때 우선순위 큐에 들어가는 값은 내림차순으로 정렬이 된다.

라운드의 횟수만큼 반복문을 진행한다. 병사의 수에서 적의 수만큼 값을 빼준다. 그리고 해당 라운드의 적의 수를 우선순위 큐에 저장한다.
이렇게 되면 큐에서 값을 가져올 때 가장 많은 적이 있는 순서대로 가져올 수 있다.

병사의 수가 0보다 작을 경우에 if문에 들어가게 되는데 여기서 한번 더 나누어진다. 무적권이라는 스킬이 있으면서 큐가 비어있지 않은 경우에는 큐에서 가장 많은 적이 있는 라운드에 스킬을 썼다고 생각하고 병사의 수에 가장 많은 적의 수를 더해준다.

예를 들어, [1, 4, 2, 1] 이라는 라운드가 있고 병사의 수는 3이라고 할 때
처음 반복을 진행하면 큐에는 1이 저장되고 병사의 수는 2가 된다. 두번째 반복을 하면 큐에는 [4, 1]이 저장되어있고 병사의 수는 -2가 된다. 이때 -2가 되면 라운드가 종료가 되므로 스킬이 있는지 여부를 판단해서 가장 많은 적이 있는 라운드에 스킬을 쓰는 것이다.

위의 예시에서는 2라운드에 스킬을 써야하므로 4라는 값이 빠져나오고 병사의 수는 -2 + 4를 해서 기존에 있던 2로 다시 바꿔준다. 이런 식으로 스킬을 써야하는 순간을 우선순위 큐를 사용해서 결정하는 것이다.

만일 스킬이 없거나 큐가 비어있을 경우에는 해당 라운드를 answer에 저장한 뒤 반복문을 break를 해준다.

위의 모든 반복이 끝난 뒤 answer에 저장되어있는 값을 반환해주면 문제를 해결할 수 있다!

💡느낀 점

최근 탐색 관련 문제만 풀다가 다른 문제를 푸니 새로웠다. 이번 문제에서 가장 중요하다고 생각되는 부분은 언제 스킬을 써야할지 구현하는 부분이었던 것 같다. 많은 고민을 해봤지만 결국 써야하는 부분은 가장 적이 많이 오는 라운드에 써야한다라는 생각에 우선순위 큐를 적용하기로 결정했다. 아직도 문제를 보면 어떤 걸 써야할지 금방금방 감이 오지 않는다.. 조금 더 열심히 많이 풀어봐야겠다..