프로그래머스 | Level 2 | 디펜스 게임

Programmers | Level 2 | 디펜스 게임

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Greedy

󰧭 Description

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

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

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

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

 Constraints

• 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 해주세요.

󰦕 Examples

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  // 큰 값 우선순위 큐
        int round = 0;
        
        for (int current : enemy) {
            pq.offer(current);  // 적 수를 우선순위 큐에 저장
            n -= current;  // 병사 수에서 적을 막기 위해 소모
            
            // 남은 병사가 부족할 경우 무적권 사용
            if (n < 0) {
                if (k == 0) break;  // 무적권이 없으면 게임 종료
                
                k--;  // 무적권 사용
                int largest = pq.poll();  // 지금까지 나온 가장 큰 적 수를 무적권으로 무시
                n += largest;  // 무적권 사용으로 병사 수를 복구
            }
            
            round++;  // 방어에 성공한 라운드 증가
        }
        
        return round;  // 막은 라운드 수 반환
    }
}

 Approaches

이 문제는 매 라운드마다 등장하는 적의 수 중에서 병사를 최대한 효율적으로 사용하고, 무적권은 가장 적이 많은 라운드에 사용하는 방식으로 탐욕법(Greedy) 접근을 적용할 수 있습니다. 각 단계에서 최선의 선택을 통해 병사 소모를 최소화하고, 가능한 한 많은 라운드를 방어하는 것이 목표입니다.

1. 문제 분석

이 문제의 핵심은 병사를 소모해 매 라운드의 적을 막는 과정에서 무적권을 최대한 효율적으로 사용하여 가능한 많은 라운드를 방어하는 것입니다. 적의 수가 클수록 병사의 소모가 많아지기 때문에 무적권은 병사 수가 부족한 라운드에서 가장 큰 적의 공격에 사용해야 합니다.

주어진 조건에서 무적권을 언제 사용해야 가장 많은 라운드를 방어할 수 있을지 고려해야 합니다. 적의 수가 큰 라운드를 우선적으로 무적권으로 처리하고, 그렇지 않으면 병사를 소모해 적을 막습니다. 게임이 끝나는 조건은 남은 병사가 적의 수보다 부족할 때이므로, 이를 전략적으로 관리하는 것이 중요합니다.

2. 접근 방식

이 문제는 그리디 알고리즘을 적용하여 해결할 수 있습니다. 각 라운드에서 등장하는 적의 수를 병사로 막다가 병사가 부족하면 무적권을 사용해 큰 적의 수를 우선적으로 처리하는 방식입니다. 이를 구현하기 위해 우선순위 큐를 사용해 지금까지 등장한 적 중 가장 큰 적을 효율적으로 선택할 수 있습니다.

• 우선순위 큐(Priority Queue): 적의 수를 저장하고, 무적권이 필요할 때는 지금까지 등장한 적 중 가장 많은 적을 무적권으로 처리하기 위해 사용합니다. 우선순위 큐는 자동으로 큰 수를 우선으로 정렬해주므로, 매번 가장 큰 적을 쉽게 찾아낼 수 있습니다.
• 무적권 사용: 병사가 부족할 때마다 무적권을 사용하여 현재까지 등장한 가장 많은 적을 무적권으로 처리하고, 병사를 복구합니다. 무적권의 사용 횟수가 다 소진되면 더 이상 라운드를 방어할 수 없게 되어 게임이 종료됩니다.

3. 적군 방어 및 무적권 사용 전략

먼저, 무적권을 사용하는 상황을 효율적으로 처리하기 위해 우선순위 큐를 초기화합니다. 이 큐는 등장한 적의 수를 내림차순으로 저장하여, 무적권을 사용할 때마다 가장 많은 적이 등장한 라운드를 선택할 수 있도록 합니다. 우선순위 큐는 최대 힙(Max Heap)의 형태로 동작하므로, 큐에서 값을 꺼낼 때 가장 큰 값을 빠르게 꺼낼 수 있습니다.

큐와 함께, 방어에 성공한 라운드 수를 기록할 변수를 초기화합니다. 이 변수는 게임을 진행하며 방어한 라운드 수를 계산하는 데 사용됩니다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  // 큰 값 우선순위 큐
int round = 0;  // 방어 성공한 라운드 수

4. 라운드 처리 및 무적권 사용 로직

각 라운드마다 등장하는 적의 수를 확인한 뒤, 병사 수에서 해당 적을 막기 위해 병사를 소모하여 남은 병사 수를 갱신합니다. 이때 적의 수는 우선순위 큐에 저장하여, 이후 가장 많은 적이 등장한 라운드를 추적할 수 있도록 합니다.

for (int current : enemy) {
    pq.offer(current);  // 등장한 적 수를 큐에 저장
    n -= current;  // 병사 수에서 적을 막기 위해 소모
    ...
}

병사를 소모한 후, 남은 병사의 수가 음수가 될 경우 이는 병사 수가 부족하여 적을 모두 막을 수 없다는 뜻입니다. 이때 무적권을 사용하여 병사의 소모를 방지할 수 있습니다. 무적권은 적의 수가 많은 라운드에서 사용하는 것이 최선이므로, 우선순위 큐를 통해 지금까지의 라운드 중 가장 많은 적이 등장했던 라운드의 적 수를 제거하고 병사 수를 회복합니다.

우선순위 큐는 등장한 적의 수를 내림차순으로 저장하며, 무적권을 사용해야 할 때마다 가장 많은 적이 등장했던 라운드를 선택해 병사를 복구합니다. 무적권을 사용할 수 없을 때, 병사의 수가 음수가 되면 게임이 종료됩니다.

무적권 사용 후 병사가 다시 회복되면, 다음 라운드를 진행합니다. 병사가 충분한 동안에는 무적권을 아끼고, 병사 수가 부족할 때만 사용하도록 로직이 구성됩니다.

for (int current : enemy) {
    ...
    
    if (n < 0) {  // 병사가 부족할 경우
        if (k == 0) break;  // 무적권이 없으면 종료
        k--;  // 무적권 사용
        int largest = pq.poll();  // 가장 큰 적 수를 무적권으로 무시
        n += largest;  // 병사 수 복구
    }
    round++;  // 방어 성공한 라운드 증가
}

5. 최종 결과 도출

모든 라운드를 차례대로 처리하면서 병사 수가 부족한 상황에서 무적권을 적절히 사용해 가능한 한 많은 라운드를 방어합니다. 만약 무적권을 모두 소진한 후 더 이상 병사로 적을 막을 수 없는 상황이 되면, 그때까지 성공적으로 방어한 라운드 수를 반환합니다.

게임이 끝나는 조건은 병사가 부족한 상태에서 무적권도 소진된 경우입니다. 이때까지 성공적으로 막은 라운드 수를 반환하며, 게임을 종료합니다.

// 방어에 성공한 라운드 수 반환
return round;

󰄉 Complexity

• ⏳ TC: O(n log n)
• 💾 SC: O(n)

각 라운드에서 적의 수를 우선순위 큐에 삽입하며, 무적권을 사용할 때는 큐에서 최대값을 꺼내기 때문에 한 번의 연산에 O(log n)의 시간이 소요됩니다. 이 과정을 n개의 라운드에 대해 반복하므로, 최종 시간 복잡도는 O(n log n)입니다. 또한, 우선순위 큐와 병사 수 정보를 저장하는 데 O(n)의 공간이 필요합니다.