프로그래머스 - 디펜스 게임

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

프로그래머스

 

 

 

 

 

문제

• 처음에 병사 n명을 가지고 있다. (1 ≤ n ≤ 1,000,000,000)
• 매 라운드마다 enemy[i] 마리의 적이 등장(1 ≤ enemy[i] ≤ 1,000,000)
  • enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있다.
• 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있다.
  • 무적권은 최대 k번 사용할 수 있다. (1 ≤ k ≤ 500,000)
• 최대 몇 라운드까지 막을 수 있는지 구하기

 

입출력 예시

• 입력 : n = 7, k= 3, enemy = {4, 2, 4, 5, 2, 3, 1}
• 결과 : 5
  • 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있다.
  • 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있다.

 

 

 

 

 

풀이

• 재귀 => 시간초과

처음에 떠오른 풀이는 재귀였다. 뒤에 어떤 애들이 오는지 모르고, 선택할 수 있는 건 무적권을 (쓸지, 안쓸지) 이다. 계속 선택을 하여 남은 병사가 없거나 무적권을 다쓰면 종료하게 한다.

 

수행시간이 2^n인데, n이 최대 100만이니 최악의 경우 2^100만이 걸린다. 시간초과가 난다.

 

내가 알고있는 알고리즘을 떠올리며 시간 초과를 막을 방법을 생각해야 하는데 안 떠오른다.. 그러다가 문제의 게시판에서 힌트를 찾을 수 있었다. (https://school.programmers.co.kr/questions/43442)

 

자료구조를 생각해야 한다.

 

• 최대힙
  • n이 0 미만이 되면, 이전 라운드에서 무적권을 써서 다시 살아난다.
  • 우선순위큐로 구현한다. 
  • 수행시간 : 삽입은 O(log n), 삭제는 O(log n)
    • 총 n(log n) 이 걸리므로, 재귀로 구현했을 때의 2^n보다 훨씬 작다.

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); //지금까지 막은 병사 수 저장
        
        int answer = 0; //정답 : 몇 라운드까지 막을 수 있는지
        for(int e : enemy) {
            n -= e; //병사로 막음
            maxHeap.add(e); //막은 병사에 저장
            
            if(n < 0) { //남은 병사가 없고
                if(k <= 0) { //무적권이 없으면
                    break; //라운드 종료
                }
                
                //아직 무적권이 있으면
                n += maxHeap.poll(); //지나온 라운드 중 가장 많은 적을 다시 부활시키기
                k--; //무적권 사용
            }
            
            answer++; //라운드 지남
        }
        
        return answer;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 수가 많을 때는 순회말고 자료구조를 생각해보기
• 최대힙 : 우선순위큐를 이용해서 구현할 수 있음

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

 

• 우선순위 큐의 수행시간 : 삽입은 O(log n), 삭제는 O(log n)