[Programmers] 디펜스 게임

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

프로그래머스

문제 설명

문제 자체는 명료하다. 적의 공격을 순서대로 막되 무적권을 활용하여 최대한 많은 라운드롤 막아내야 한다.

문제를 잘 이해했다면 무적권은 가능한 적이 많을 때 사용하는 것이 효율적이라는 것을 알 수 있다. 그렇다면 그 '가능한 적이 많을 때' 를 어떻게 처리해야 할까? 처음에는 정렬을 이용해서 해결하려고 했다. enemy를 내림차순 정렬하고 k + 1번째부터 시작하는 식으로 접근했다. 그러나 이렇게 하면 7, 3, [5, 5, 5, 5, 2, 3, 1] -> 5 케이스에서 문제가 생긴다. 3라운드까진 무적권으로 통과하고 4, 5라운드까지 통과하여 최대 5라운드여야 한다. 하지만 정렬을 할 경우 [5, 5, 5, 5, 3, 2, 1] 이 되어 4라운드까지밖에 통과하지 못한다. 이 문제를 해결하기 위해 생각하던 중 힙을 활용하라는 팁을 보고 정렬 대신 힙으로 문제를 해결했다.

힙은 최솟값 또는 최댓값을 효율적으로 저장하고 탐색하기 위한 자료구조이다. 이를 이 문제에 활용하려면 무적권을 활용하는 방법을 조금 달리 봐야 한다. 처음엔 무적권 개수만큼 뛰어넘도록 했다. 하지만 다른 방법으로 n이 0보다 작아지면 지난 적들의 수 중 가장 많았던 만큼 더해주는 방법도 사용해볼 수 있다. 위 케이스의 경우는 다음과 같은 흐름이 된다.

1. n = 7 - 5 = 2, 힙 = [5] -> n이 0보다 크므로 패스
2. n = 2 - 5 = -3, 힙 = [5, 5] -> n이 0보다 작으므로 무적권을 써서 5를 더함 -> n = 2, 힙 = [5]
3. n = 2 - 5 = -3, 힙 = [5, 5] -> n이 0보다 작으므로 무적권을 써서 5를 더함 -> n = 2, 힙 = [5]
4. n = 2 - 5 = -3, 힙 = [5, 5] -> n이 0보다 작으므로 무적권을 써서 5를 더함 -> n = 2, 힙 = [5]
5. n = 2 - 2 = 0, 힙 = [5, 2] -> n이 0과 같으므로 패스
6. n = 0 - 3 = -3, 힙 = [5, 3, 2] -> n이 0보다 작으나 무적권을 모두 사용했기 때문에 종료

코드

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < enemy.length; i++) {
            n -= enemy[i];
            heap.offer(enemy[i]);
            
            if (n < 0) {
                if (k > 0) {
                    n += heap.poll();
                    k--;
                } else {
                    break;
                }
            }
            
            answer++;
        }
        
        return answer;
    }
}