프로그래머스, 디펜스 게임(java)

문제 설명

병사 n명과 무적권을 쓸 수 있는 횟수 k가 주어진다. 한 라운드씩 적들을 막아야 하는데, 적을 막을 경우 병사가 해당 적들의 수만큼 사라진다. 그러나 무적권이라는 스킬을 쓰면 병사를 소모시키지 않고 해당 라운드를 넘어갈 수 있다. 이때 최대로 지나갈 수 있는 라운드를 구하는 문제이다.

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

프로그래머스

문제 풀이

첫 번째 접근

처음에는 백트랙킹으로 풀었다. 모든 경우의 수를 확인하지만, 조건에 맞지 않으면 해당 경로를 더이상 탐색하지 않는 방법 말이다. 그러나 재귀 함수의 깊이가 너무 깊은 건지 런타임 에러가 났다.

두 번째 접근

백드랙킹 아니면 뭘로 풀어야 할지 몰라서 방법을 찾아보니 우선순위 큐로 푸는 방법이 있었다.

https://school.programmers.co.kr/questions/43442

프로그래머스

위의 해설은 일단 n에서 적을 빼준다. 그리고 만일 n이 0보다 작아지면 지난 라운드에서 제일 적이 많았던 라운드를 찾아서 해당 라운드에 무적권을 쓰는 방식이다. 이때 지난 라운드에서 제일 적이 많은 라운드는 우선순위 큐를 사용한다. 우선순위 큐를 내림차순으로 정렬해야 하는데, 이때는 음수를 이용하면 쉽게 구할 수 있다.

코드

java

import java.util.*;

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