디펜스 게임

문제 설명
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

시도했던 로직

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) { 
        int answer = 0;
        int[] skip = new int[k];
        if(k>enemy.length)
            return enemy.length;
        for(int i=0; i<k; i++)
            skip[i] = enemy[i];
        answer = k;
        if(k>1)
        Arrays.sort(skip);
        for(int i=k; i<enemy.length;i++){
            if(skip[0]<enemy[i]){
                n = n-skip[0];
                if(n<0)
                    break;
                answer++;
                skip[0] = enemy[i];
                if(k>1&&enemy[i]>skip[1])
                    Arrays.sort(skip);
            }
            else if(n >= enemy[i]){
                n = n - enemy[i];
                answer++;
            }
            else if(n<enemy[i])
                break;
        }
        return answer;
    }
}

• 배열에 무적권을 사용한 라운드의 병사 수를 기록하고, 배열의 최소값을 활용하여 최적의 경우의 수를 찾도록 구현하였는데, 최소값을 찾는 과정에서 배열을 정렬하게되는데, 이 때문에 시간초과가 발생하였다. 그래서 배열 정렬을 최소화 하도록 코드를 계속 수정해도 시간초과는 막을 수 없었다.
  

해결한 로직(PriorityQueue으로 해결)

• 배열로 구현하는 것 보다 시간이 빠른 방법을 찾아보고,
  Priority Queue(우선 순위 큐)를 사용하는 방법을 알게 되었다.

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;
    }
}

• PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
• 데이터가 들어가면서 정렬이 동시에 되는 형태이기 때문에 기존의 배열을 정렬하는 로직보다 훨씬 시간이 빠르다.
  

오늘의 회고

물론, 알고리즘 문제를 많이 풀진 않았지만, 여태까지는 시간복잡도에 걸려본 경험이 없었는데,
이 문제를 풀면서 느꼈다.
알고리즘 문제를 많이 풀면서 경험을 쌓고, 다양한 자료구조형들에 익숙해 져야겠다.