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

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

 

🔍  해결 과정

무적권을 사용하는 기준을 생각하는 과정에서 시간이 걸렸던 문제입니다. 조합을 활용하여 무적권을 일일이 선택하여 계산하기에는 enemy의 길이가 최대 100만이므로 유효 시간 안에 연산을 완료할 수가 없습니다.

 

그래서 강구한 다른 방법은 우선순위 큐를 활용하여 현재까지 나온 적의 수 중 가장 많은 적이 나타난 것에 무적권을 부여하는 것입니다.

자세한 설명은 코드에 주석을 통해 첨부하였습니다.

 

• 시간복잡도: O(mlogm), m: enemy 배열의 길이
• 우선순위 큐 자료구조의 시간 복잡도: O(logm)

---

✏️ 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        // 적이 많은 순으로 우선순위 큐를 처리
        Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
        
        for (int e : enemy) {
            pq.offer(e); // 적의 수를 큐에 넣어두기
            n -= e;
            
            // n이 음수라면 무적권 사용하기
            if (n < 0) {
                int roundCount = 0;
                
                while (n < 0 && k > 0) {
                    n += pq.poll();
                    --k; // 무적권 사용
                    ++roundCount;
                }
                
                // 이랬는데도 n이 여전히 음수라면 게임이 종료
                if (n < 0) {
                    break;
                }
                
                // 그런게 아니라면 무적권 사용한 만큼 라운드 계산하기
                answer += roundCount;
                continue;
            }
            
            // n이 양수이면 라운드 진행이 가능함.
            ++answer;
        }
        
        return answer;
    }
}