디펜스 게임(프로그래머스-연습문제)

문제

코드

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer=0;
        Queue<Integer> pq=new PriorityQueue<>((a,b)->b-a);
        int i=0;
        while(true){
            if(i==enemy.length) break;
            n-=enemy[i];
            pq.add(enemy[i]);
            if(n<0&&k>0&&!pq.isEmpty()){
                n+=pq.poll();
                k--;
            }
            if(n>=0){
                i++;
                answer++;
            }
            if(n<=0&&k==0) break;
        }
        return answer;
    }
}

풀이

(1) 일단 라운드를 진행하고, 적의 수만큼 n을 뺀다.
(2) 만약 n<0 이고, k>0이면 지금까지 진행했던 라운드 중 가장 적의 수가 많았던 라운드의 적의 수 만큼 n에 더해주고, k에서 1을 뺀다.
(3) 위처럼 진행 후에, n>=0이면 answer에 1을 더해주고, 다음 라운드를 진행한다. 만약 n<0 이고, k==0 이면 게임을 종료한다.

결과

처음에는 dfs를 생각했다. "어차피 무적권을 쓰거나 안쓰거나 둘중 하나 아닌가?" 라는 생각에서, 무적권을 쓰는경우와 쓰지않는 경우를 계속 탐색하며 모든 경우의 수를 실행했다. 하지만, 시간 초과가 났다.
사실, 제한사항을 보면 수가 너무 컸기 때문에 어느정도 예상은 하고 있었지만, 이 방법이 아니면 생각나지 않았다.

도저히 생각나지 않아서 힌트를 봤더니, 우선순위 큐를 사용하는 문제였다. 지나온 라운드 중 가장 많았던 적의 수만큼 체력을 회복하는 방식으로 무적권을 사용한다는 것이다.

내 머리로는 이 정도까지 생각할 수 없는건가 싶다. 아마 방법을 생각해 냈다 해도, 우선순위 큐 자료구조를 사용한다는 생각을 못했을 것 같다.
이런 문제는 풀이법을 외우는 것 아니면, 다음에 나오면 또 풀 수 있을 것이라는 생각이 들지 않는다.
그래도 뭐 하다보면 사고력이 늘겠지 하는 마음으로 계속 공부한다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges