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

문제 주소

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

프로그래머스

문제 설명

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

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

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

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

---

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

---

입출력 예

n k enemy result

7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

---

입출력 예 설명

입출력 예#1

• 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.

입출력 예#2

• 준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

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

제출 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)-> o2-o1);
        
        for(int i=0;i<enemy.length;i++){
            
            q.add(enemy[i]);
            n = n - enemy[i];
            
            if(n>=0){
                answer++;
            }else{//n-enemy[i]이 0보다 작아졌을 때 나온것 중에 제일 큰 것에 무적권 적용함
                if(k>0){
                    k--;
                    n += q.poll();//나왔던 것중에 제일 큰 것만큼 더하고 현재것 빼줌
                    if(n>=0){
                        answer++;
                    }
                }
            }
            
            if(n<0&&k<=0){
                break;
            }
   
        }

        return answer;
    }
}

코드 설명

PriorityQueue를 사용해서 여태까지 나온 enemy의 element들 다 저장해줌

n에서 매 회차 enemy[i]만큼 빼줌

그게 0보다 작다면 PriorityQueue에서 제일 큰거 하나 poll해서 여태까지 나온것중에 제일 큰 것에 무적권 적용하고 

무적권 적용한 숫자만큼 n에다 더 더해줌

 

풀이과정

처음에는 PriorityQueue 안 쓰고 k개의 max를 가지고있다가 무적권 쓰는 방식으로 함

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        int [] max = new int [k];
        int [] maxIdx = new int[k];
        
        for(int i=0;i<k;i++){
            max[i] = -1;
            maxIdx[i] = 0;
        }
        
        
        //k개의 가장 큰 원소 인덱스들 구함
        for(int i=0;i<enemy.length;i++){ 
            int min = Integer.MAX_VALUE;
            int minIdx = 0;
            for(int j=0;j<max.length;j++){
                if(min>max[j]){
                    min = max[j];
                    minIdx = j;
                }
            }
            if(min<enemy[i]){
                max[minIdx] = enemy[i];
                maxIdx[minIdx] = i;
            }
        }
        
        int superIdx = 0;
        for(int i=0;i<enemy.length;i++){
            
            boolean superpass = false;
            
            if(superIdx<maxIdx.length&&i==maxIdx[superIdx]){
                superIdx++;
                superpass = true;
                answer++;
            }
            
            if(superpass){
                continue;
            }
            
            if(n-enemy[i]>=0){
                n = n - enemy[i];
                answer++;
            }
            
            if(n<0&&superIdx<maxIdx.length){
                break;
            }
   
        }

        return answer;
    }
}

비효율적인건 둘째치고 

제일 큰 원소가 나중에 있고 n이 다 떨어졌을시에 제일 큰 원소는 나오지도 않았는데 거기다가 우선적으로 무적권을 적용해버리는 문제가 있었음

테스트 1 〉	실패 (48.46ms, 78.1MB)
테스트 2 〉	실패 (147.06ms, 100MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (188.83ms, 84.7MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (7936.49ms, 138MB)
테스트 8 〉	실패 (1357.57ms, 126MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	통과 (6799.89ms, 129MB)
테스트 11 〉	실패 (142.86ms, 129MB)
테스트 12 〉	실패 (145.58ms, 125MB)
테스트 13 〉	통과 (0.04ms, 77.5MB)
테스트 14 〉	통과 (0.05ms, 74.3MB)
테스트 15 〉	통과 (0.02ms, 69.8MB)
테스트 16 〉	실패 (0.04ms, 76.9MB)
테스트 17 〉	통과 (0.02ms, 71.1MB)
테스트 18 〉	통과 (0.04ms, 78.6MB)
테스트 19 〉	통과 (0.01ms, 74.8MB)
테스트 20 〉	통과 (0.02ms, 73.9MB)
테스트 21 〉	통과 (0.03ms, 76.5MB)
테스트 22 〉	통과 (0.05ms, 76.3MB)
테스트 23 〉	실패 (0.07ms, 77.1MB)
테스트 24 〉	실패 (0.08ms, 74.9MB)
테스트 25 〉	실패 (0.04ms, 76.9MB)
테스트 26 〉	실패 (0.16ms, 72.6MB)
테스트 27 〉	실패 (0.11ms, 77.5MB)
테스트 28 〉	통과 (0.10ms, 81.6MB)
테스트 29 〉	실패 (0.41ms, 71.9MB)
테스트 30 〉	실패 (0.22ms, 74.4MB)
테스트 31 〉	실패 (0.33ms, 73.8MB)
테스트 32 〉	실패 (0.32ms, 77MB)

 

이거랑 비슷한 문제 뭐 있지 하다가

광물찾기랑 느낌 비슷해서 광물찾기 내 코드 보고 PriorityQueue 쓰기로 함

PriorityQueue에다 정렬하면서 해봄

cost가 제일 높은게 제일 위로 오도록 정렬해봄…

n을 초과하게 되는 순간 PriorityQueue에서 뽑아서 여태까지 제일 컸던거 무적권 처리하고 넘어가면 될듯?

 

바꿔주고 통과함

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)-> o2-o1);
        
        for(int i=0;i<enemy.length;i++){
            
            q.add(enemy[i]);
            n = n - enemy[i];
            
            if(n>=0){
                answer++;
            }else{//n-enemy[i]이 0보다 작아졌을 때 나온것 중에 제일 큰 것에 무적권 적용함
                if(k>0){
                    k--;
                    n += q.poll();//나왔던 것중에 제일 큰 것만큼 더하고 현재것 빼줌
                    if(n>=0){
                        answer++;
                    }
                }
            }
            
            if(n<0&&k<=0){
                break;
            }
   
        }

        return answer;
    }
}