코딩 테스트 [프로그래머스] - 디펜스 게임

문제 링크

우선순위 큐를 이용해 문제를 풀었다.

진행할 수 있는 최대 라운드 수를 구하려면 유저가 겪는 라운드 중 가장 큰 웨이브를 무적권을 사용해서 막으면 된다.

유저가 게임을 더이상 진행할 수 없게 된다면 그 때 지금까지 겪은 웨이브에서 가장 큰 웨이브에 무적권을 사용한것으로 가정하고 게임을 이어서 하면 된다.

이를 위해 유저가 겪은 웨이브를 큐에 저장하고,
그중 가장 큰 웨이브를 구하기 위해 우선순위 큐를 이용한다.

---

전체 코드는 다음과 같다.

import java.util.*;

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

---

먼저 내림차순으로 수를 저장하는 우선순위 큐 queue를 만들었다.

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

무적권의 갯수 k가 적의 공격 횟수인 enemy.length보다 크다면 무적권으로 모든 공격을 막을 수 있으므로 적의 공격횟수를 반환한다.

        if(k >= enemy.length){
            answer = enemy.length;
            return answer;
        }

적의 공격 횟수만큼 반복문을 돌리며 적의 공격을 막을 수 있는지 확인한다.

        for(int i = 0; i < enemy.length; i++){
            ...
        }

겪은 적의 공격을 우선순위 큐 queue에 넣는다.
그 후 병사를 소모해 적의 공격을 막는다.

        for(int i = 0; i < enemy.length; i++){
            queue.add(enemy[i]);
            n -= enemy[i];
            
            ...
        }

적의 공격을 막았을 때 병사의 수가 0보다 크거나 같다면 공격을 막아낸것이므로 정답을 1 증가시킨다.

        for(int i = 0; i < enemy.length; i++){
            queue.add(enemy[i]);
            n -= enemy[i];
            
            if(n >= 0){
                answer++;
            }
            ...
        }

만약 병사의 수가 0보다 적다면 공격을 막아내지 못한것이 된다. 이 때는 무적권이 남아있는지 확인한다.

        for(int i = 0; i < enemy.length; i++){
            queue.add(enemy[i]);
            n -= enemy[i];
            
            if(n >= 0){
                answer++;
            }else{
                if(k > 0){
                    ...
                }else{
                    ...
                }
            }
        }

무적권이 남이있지 않다면 더이상 게임을 진행할 수 없으므로 반복문을 빠져나오고 정답을 반환한다.

        for(int i = 0; i < enemy.length; i++){
            queue.add(enemy[i]);
            n -= enemy[i];
            
            if(n >= 0){
                answer++;
            }else{
                if(k > 0){
                    ...
                }else{
                    break;
                }
            }
        }
        
        return answer;

무적권이 남아있다면 무적권을 사용해 지금까지 경험한 공격 중 가장 큰 공격에 무적권을 사용한것으로 가정하고 게임을 진행한다.

경험한 공격은 queue에 저장되어 있고, queue는 내림차순으로 정렬되어 있으므로 바로 poll()을 하면 가장 큰 공격이 나오게 된다.

가장 큰 공격에 무적권을 사용했으므로 무적권 수를 1 줄이고
병력 수에 무적권으로 막은 공격만큼 더해준다.
정답도 1 증가시켜준다.

        for(int i = 0; i < enemy.length; i++){
            queue.add(enemy[i]);
            n -= enemy[i];
            
            if(n >= 0){
                answer++;
            }else{
                if(k > 0){
                    k--;
                    n += queue.poll();
                    answer++;
                }else{
                    break;
                }
            }
        }
        
        return answer;

---

같은 아이디어를 단순 반복문을 이용해 풀었다가 몇가지 테스트케이스에서 타임아웃이 나와, 정답을 찾아보고 우선순위 큐를 사용한다는 것을 알게 되었다.