[연습 문제] 디펜스 게임 - JAVA

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

프로그래머스

---

딱 봐도 모든 경우의 수를 다 찾는건 무리라고 생각이 들고...

이걸 어쩌지.. 하다가 찾아보니까 좋은 방법이 있었따!

 

지금까지 뺀 값들 중에서 가장 큰 값을 롤백하는 방법이다!

이게 무슨말이냐면 우선 적의 수를 순서대로 우선순위 큐에 저장한다

그리고 만약 병사의 수가 0보다 적으면 무적권을 사용하는 것이다

이 때 무적권은 우선순위 큐에 저장된 적의 수 중에서 가장 큰 값에 대해서 사용한다

 

아래는 코드니까 보면 더욱 이해가 빠르게 될 것이다 :)

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = enemy.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < enemy.length; i++) {
            n -= enemy[i];
            pq.add(enemy[i]);

            if(n<0) {
                if(k>0) {
                    n += pq.poll();
                    k--;
                    continue;
                }
                answer = i;
                break;
            }
        }
        return answer;
    }
}

---

참고)

https://velog.io/@sheltonwon/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%94%94%ED%8E%9C%EC%8A%A4-%EA%B2%8C%EC%9E%84-JAVA

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