[프로그래머스][JAVA] 디펜스 게임

링크

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

프로그래머스

 

 

설명

일단 무적권이 적을 쓰려트려야하는 라운드 수보다 많은 경우에는 무적권만 써도 게임을 클리어 할 수 있습니다. 

if (k >= enemy.length) -> enemy.length 

 

그렇지 않은 경우에는 일단 무적권을 쓰고 적과의 전투도 필요한 경우입니다.

해당 경우에는 각 라운드의 전투에서 무적권을 쓸지 적으로 전투할 지 결정해야 합니다.

 

BFS로 한다면 병사의 수가 너무 많기 때문에 시간 내에 풀 수 없습니다.

따라서, 우선순위 큐에 무적권에 관한 정보를 저장하는 방식으로 풀어봅니다.

1. 우선순위 큐에 각 라운드의 적의 숫자를 넣어두고 일단 무적권만큼 라운드를 진행합니다.
2. 다음 라운드에 왔을 때 무적권을 쓴 가장 적은 숫자의 적을 한번 꺼내봅니다.
3. 무적권을 쓴 가장 적은 숫자의 적이 현재 라운드의 적의 숫자보다 낮다면 실드권 변경이 필요합니다.
    (현재 라운드의 적에게 무적권을 쓰고 가장 적은 숫자의 적은 아군 솔저의 수에서 감소 시켜줍니다.)
4. 그렇지 않다면 현재 라운드를 그냥 진행합니다.
5. 아군 솔저의 숫자가 적보다 적어진다면 (<0) 해당 라운드가 마지막 라운드 입니다.

 

라운드를 모두 진행하고 나서도 아직 괜찮다면 아군 솔저의 수가 더 많이 남아있어서 이긴 경우입니다.

enemy.length

 

풀이

BFS 실패 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        // 4 6 10 15 18 21 22
        // sumEnemy <= n -> enemySize
        // enemySize <= k -> enemySize
        int sumEnemy = 0;
        for (int i=0; i<enemy.length; i++) {
            sumEnemy += enemy[i];
        }
        
        if (sumEnemy <= n) {
            return enemy.length;
        }
        
        if (enemy.length <= k) {
            return enemy.length;
        }
        // bfs
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, k, 0, 0});
        int answer = 0;
        while(!q.isEmpty()) {
            int[] eInfo = q.poll();
            int soldiers = eInfo[0];
            int shields = eInfo[1];
            int cEnemyIndex = eInfo[2];
            int cEnemy = enemy[cEnemyIndex];
            int round = eInfo[3];
            if (soldiers < 0 && shields == 0) {
                answer = Math.max(answer, round-1);
                continue;
            }
            
            if (shields > 0) {
                // 무적권 쉴드 사용
                q.add(new int[]{soldiers, shields-1, cEnemyIndex + 1, round + 1});
            }
            
            // 솔저랑 적 대치
            if (soldiers > 0) {
            q.add(new int[]{soldiers - cEnemy, shields, cEnemyIndex + 1, round + 1});
            }
            
        }
        
        return answer;
    }
}

 

성공 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        // k >= enemyLen 바로 return
        if (k >= enemy.length) {
            return enemy.length;
        }
        
        // k만큼 q에 넣는다.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i=0; i<k; i++) {
            pq.add(enemy[i]);
        }
        
        int totalEnemy = n;
        for (int i=k; i<enemy.length; i++) {
            int lastShieldEnemy = pq.poll();
            int curEnemy = enemy[i];
            // 실드권 변경
            if (lastShieldEnemy < curEnemy) {
                pq.add(curEnemy);
                totalEnemy -= lastShieldEnemy;
            } else {
            // 적 공격
                pq.add(lastShieldEnemy);
                totalEnemy -= curEnemy;
            }
            
            if (totalEnemy < 0) {
                return i;
            }
        }
        
        // 아직 아군이 더 많은 경우
        return enemy.length;
    }
}