디펜스 게임 - 구현

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

프로그래머스

[문제 설명]

1. 본인은 병사 n명을 가지고 디펜스 게임을 한다.

2. 매 라운드 마다 enemy[i] 마리의 적이 등장한다. ( ex) 남은 병사가 7명이고 적이 2명일 경우, 7-2=5명의 병사가 남음)

3. 남은 병사의 수보다 현재 라운드의 적이 더 많으면 게임 종료

 

● 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 무적권 막을 수 있다.

● 무적권은 최대 K번 무적권 사용할 수 있다. (무적권 가능)

 

무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 최대 진행 라운드를 반환하라.

 

[문제 풀이]

처음에는 dfs 문제인줄 알았으나, 생각보다 간단한 문제였다.

문제에서는 무적권을 해당 라운드에서만 사용해야 할 것처럼 설명하고 있다. 그러나 문제 해결적 관점에서 보자면 지나온 라운드에도 무적권을 사용해도 무적권 상관없다. 본인은 Heap 배열을 사용해서 해결했다.

 

1. 일단 지나가며 n보다 작은 적들을 n에서 차감 후 heap 에 저장한다.

2. 이후 n보다 큰 적을 만난다면 이때 무적권을 써야하는 타이밍이다.

3. 무적권을 썼다면 heap 배열에서 가장 큰값을 반환하여 n에 더하여 좀 더 게임이 진행되도록 한다.

4. 무적권을 다쓰고 만난 적이 더 값이 크다면 해당 위치까지의 길이를 반환한다.

 

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
        public int solution(int n, int k, int[] enemy) {
            int answer = enemy.length;
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
            
            for (int i = 0; i < enemy.length; i++) {
                n -= enemy[i];
                maxHeap.add(enemy[i]);
                
                if (n < 0) {
                    if (k > 0) {
                        try {
                        n += maxHeap.poll();
                        k --;
                        } catch (NullPointerException e) {
                            answer = i; break;
                        }
                    } else {
                        answer = i; break;
                    }
                }
            }
            return answer;
        }
    }