🔥[99클럽 코테 스터디] 38일차 TIL - 디펜스 게임

⏳문제

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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	resut
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) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int answer = 0;
        
        if (k >= enemy.length) {
            return enemy.length;
        }
        
        // 초반에 무적권 다 사용
        for (int i = 0; i < k; i++) {
            pq.add(enemy[i]); // 무적권 사용
            answer++; // 막아낸 라운드 증가
        }

        for (int i = k; i < enemy.length; i++) {
            if (pq.peek() < enemy[i] && pq.peek() <= n) {
                n -= pq.poll(); // 남은 병사로 막아내기
                pq.add(enemy[i]); // i번째 라운드에 대한 무적권 사용
                answer++; // 막아낸 라운드 개수 증가
            }
            else {
                if (enemy[i] > n) {
                    return answer; // 더 이상 진행 불가
                }
                else {
                    n -= enemy[i]; // 남은 병사 수 업데이트
                    answer++; // 막아낸 라운드 개수 증가
                }

            }
        }
        return answer;
    }
}

👾코드 설명

1. 무적권의 개수가 모든 라운드의 길이 이상이면, 모든 라운드를 무조건 클리어 할 수 있기 때문에 라운드의 길이를 그대로 리턴한다.

2. 일단 초반에 무적권을 모두 사용(우선 순위 큐에 모두 추가)하고, 막아낸 라운드의 개수 answer도 증가시켜 준다.

3. 무적권을 사용한 라운드 중 최소값(pq에서 peek()한 값)보다 현재 i번째 라운드의 적의 수가 더 많고, peek()한 라운드를 현재 병사의 수로 클리어할 수 있다면, 해당 라운드를 pq에서 poll()해 남은 병사 n으로 막아내고, 현재 i번째 라운드에 대한 무적권을 사용한다. (answer 증가)

4. 3번 조건에 부합하지 않아 무적권을 더 이상 사용할 수 없고, 현재 i번째 라운드의 적의 수가 남은 병사보다 많다면, 더 이상 라운드를 진행할 수 있는 방법이 없기 때문에 현재까지 막아낸 라운드의 개수 answer를 반환한다.

5. 3번 조건에 부합하지 않아 무적권을 더 이상 사용할 순 없지만, 현재 i번째 라운드의 적의 수가 남은 병사보다 적다면, 남은 병사로 라운드를 더 진행할 수 있기 때문에 n의 값을 enemy[i]만큼 감소시켜 준다. (answer 증가)

---

🔗문제 링크
💻Repository