[PS] 99클럽 코테 스터디 38일차 TIL (디펜스 게임)

문제

문제 링크

설명

준호가 가진 병사(n) 와 ‘무적권’ k 개를 이용해 몇 enemy 배열의 몇번째 인덱스까지 갈 수 있는지 확인하는 문제

풀이

1. 무적권은 최대한 적군이 많은 라운드에 사용하는 것이 유리하다. -> PriorityQueue 로 무적권을 사용 할 적군 수를 결정하기 위해 최대 힙을 사용한다.
2. 각 라운드마다 적의 수를 maxHeap 에 저장하고, n 에서 적군 수를 제거하면서 진행한다.
3. 준호가 가진 병사의 수가 모두 소진되면, maxHeap 에서 최대값을 꺼내(maxHeap.poll()) 라운드를 통과할 수 있도록 한다.
   • ‘무적권’ 을 사용한다는 의미 : 힙에서 꺼낸 값을 다시 n 에 추가한다. 즉, 준호의 병사를 보충한다.
   • ‘무적권’ 을 사용했으므로 -1 하고, 다음 라운드로 넘어갔다는 의미로 answer 를 +1 해준다.
   • 만약 준호의 병사도 없고(n < 0), ‘무적권’도 없다(k < 0)는 의미는 더이상 진행이 불가능 한 경우이므로 break

class Solution {
  public int solution(int n, int k, int[] enemy) {
    int answer = 0;
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int i = 0; i < enemy.length; i++) {
      maxHeap.add(enemy[i]);
      n -= enemy[i];

      if (n < 0) {
        if (k > 0) {
          n += maxHeap.poll();
          k--;
        } else {
          break;
        }
      }
      answer++;
    }
    return answer;
  }
}