문제

문제링크

접근

• enemy의 길이가 짧지만은 않아서 모든 경우의 수를 따지기에는 부담이 따를 것이라고 예상했다.
• 사고의 흐름은 지금까지의 뺀 값들 중에 가장 큰 것을 롤백한다는 상상이 먼저 떠올랐다.
• 그래서 거쳐온 모든 값을 저장해놓고, 그 중에 최대값을 다시 복구하는 순서로 구현하였다.
• 최대값을 얻는 방법은 저장할 때부터 우선순위큐에 넣는 방법으로 구현하였다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = enemy.length;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        int my = n;
        int card = k;
        for (int i = 0; i < enemy.length; i++) {
            my -= enemy[i];
            pq.add(enemy[i]);

            if (my < 0) {
                if (card > 0 && !pq.isEmpty()) {
                    my += pq.poll();
                    card--;
                } else {
                    answer = i;
                    break;
                }
            }
        }

        return answer;
    }
}