[프로그래머스/Lv.2] 디펜스 게임 - Java

문제

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

프로그래머스

 

 

리뷰

그동안 여러 코딩 테스트에 많이 나왔을 법한 문제였다. 이번 기회로 확실히 풀이를 기억해 두어야겠다.

풀이 아이디어가 떠오르지 않아서 일단 재귀를 통한 완전탐색을 해봤다. 문제의 제한사항이 아래와 같으니 당연하게도 시간 초과가 발생했다.

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000

시간 효율성을 개선하기 위해 다양한 방법을 생각해봤다. 매 라운드마다 enemy의 수가 달라서 DP는 어렵다고 생각했다. 또한 현재 라운드에서 '무적권'을 사용하느냐 마느냐가 다음 라운드를 진행하는 데 영향을 주므로 그리디도 아니었다.

 

 

풀이

답은 우선순위 큐였다. 기본적인 로직은 아래와 같다.

1. '무적권'이 없다고 생각하고 일단 싸운다.
2. 싸웠을 때 물리친 적의 수(enemy[i])를 우선순위 큐에 넣는다.
3. 싸우고 남은 병사의 수(n)가 0보다 작을 때
   1. k > 0인 경우: 우선순위 큐의 맨 앞(=가장 많이 물리친 적의 수)의 값을 더해준다. 즉, 여태까지 적을 가장 많이 물리친 라운드에 '무적권'을 썼다고 치는 것이다. '무적권'을 사용했으므로 k에서 1을 뺀다.
   2. k ≤ 0인 경우: 아무것도 하지 않는다.
4. 3을 마쳤을 때 n을 한 번 더 확인한다.
   1. n ≥ 0인 경우: answer에 1을 더하고 다음 라운드로 넘어간다.
   2. n < 0인 경우: 게임을 종료한다.

 

코드

import java.util.*;

class Solution {
    
    int totalRound = 0;
    Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        totalRound = enemy.length;    
        for(int i = 0;i<totalRound;i++) {
	    // '무적권'이 없다고 치고 일단 싸운다.
            pq.offer(enemy[i]);
            n-=enemy[i];
            
            // 싸운 뒤의 병사 수가 0보다 작은데 '무적권'이 남아있으면
            if(n < 0 && k > 0){
            	// 가장 많은 병사를 물리친 라운드에서 무적권을 썼다고 친다.
                n+=pq.poll();	
                k-=1;
            }
            
            if(n>=0) {
                answer+=1;
            }else{
                break;
            }
        }
        
        return answer;
    }
}