[Programmers] 디펜스 게임 / ❌

 

프로그래머스

1. 제출 코드 (1시간 15분 57초 / 우선순위 큐)

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o1 - o2;
        });
        
        for(int i = 0; i < Math.min(k, enemy.length); i++) {
            pq.add(enemy[i]);
        }
        
        for(int i = Math.min(k, enemy.length); i < enemy.length; i++) {
            if(enemy[i] > pq.peek()) {
                n -= pq.poll();
                pq.add(enemy[i]);
            } else {
                n -= enemy[i];
            }
            if(n < 0) {
                break;
            }
            answer++;
        }
        answer += pq.size();
        return answer;
    }
}

 

2. 구현 로직

1. pq를 만들어 무적권 스킬을 사용하는 값을 담아두려고 한다.
2. enemy의 앞쪽부터 무적권 스킬을 사용하여 pq에 오름차순으로 넣는다.
3. 그럼 K 이후의 enemy를 탐색하며 pq의 가장 앞에 숫자와 비교한다.
4. 만약, pq의 가장 앞 숫자보다 enemy[i]의 값이 크다면 pq의 값을 빼고 enemy[i]를 넣는다.
5. 그게 아니라면 n의 값을 enemy[i] 만큼 감소시킨다.
6. n < 0 보다 작으면 종료한다.

 

3. 유의할 점

• 처음에 N의 값을 확인하고도 긴가민가 해서 백트래킹으로 시도했는데 역시나 시간복잡도 문제로 풀리지 않았다. 확신을 가지고 문제를 풀도록 해야겠다.