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

https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

[문제]

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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 해주세요.

 

[코드]

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        int power=n;
        int card=k;
        
        // 공격력이 높은 순서대로 정렬
        PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0;i<enemy.length;i++){
            pq.add(enemy[i]); // 제거한 병사 수 저장
            power-=enemy[i]; // 공격력 감소
            
            // 공격력을 다 잃었다면
            if(power<0){
                if(card>=1) { // 무적권이 남아 있다면 
                    power+=pq.poll(); // 여태까지 제거한 병사 수 중 가장 큰 값을 다시 더해줌
                    card--;
                }
                else // 남은 무적권이 없는 경우
                    return answer; // 결과 값 return      
            }
            
            answer++; // 라운드 수 증가 
        }
        return answer;
    }
}

 

[고찰]

 이번 문제는 우선순위 큐에 여태까지 공격한 병사의 수를 내림차순으로 저장 후 공격력을 다 잃은 경우 가장 큰 값을 큐에서 꺼내 다시 병사 수를 증가시켜 주고 공격권의 수를 감소시키면 되는 문제였다. 우선순위 큐를 써야한다는 아이디어가 떠오르지 않아 다른 사람의 포스팅을 참고했는데 자료구조의 시야를 좀 더 넓혀야겠다.