[프로그래머스][Java][Lv. 2] 디펜스 게임

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

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

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> enemyQueue 
            = new PriorityQueue<>(Collections.reverseOrder());
        int answer = 0;
        
        for (int i = 0; i < enemy.length; i++) {
            if (enemy[i] <= n) {
                enemyQueue.add(enemy[i]);
                n -= enemy[i];
            } else {
                if (0 < k) {
                    if (!enemyQueue.isEmpty() 
                        && enemy[i] <= enemyQueue.peek()) {
                        n += (enemyQueue.poll() - enemy[i]);
                        enemyQueue.add(enemy[i]);
                    }
                    k--;
                } else break;
            }
            answer++;
        }
        return answer;
    }
}

 

---

 

후기

보자마자 우선순위큐를 사용해야 겠다고 생각했는데 통과되고 나서 보니까 대부분 다 그렇게 생각했나보다. 기본적인 흐름은 enemy[i]보다 n이 크면 n에 enemy[i]를 빼고 큐에 넣고, n이 enemy[i]보다 작으면 큐에서 이전의 것을 꺼내와 그것에 무적권을 사용하는 방식이다. 쉽게 말하면 일단 그냥 무식하게 적을 잡다가 나보다 강한 적을 만나면 '아 내가 과거에 무적권을 썼으면 얘는 잡았을텐데'라는 것을 과거의 강한 적에게만 돌아가기해서 무적권을 사용하는 것이다.

 

처음에 접근은 잘했지만 제출하는데 계속 6번과 21번만 틀려서 뭔가 싶었는데 생각해보니 이전 내역 중 가장 큰 수가 현재의 enemy[i]보다 작으면 뒤의 적에 무적권을 사용하는 의미가 없다. 현재 적에게 무적권을 사용해야 한다는 점을 생각하지 못해서 그런거였다.