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

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

🔗 문제 링크

---

문제 설명 📄

n개의 병력을 가지고 있으며, enemy 리스트에 나타나는 적들과 매 라운드 전투를 진행해야 한다.
단, 최대 k번은 병력을 사용하지 않고 방어할 수 있다.
방어 기회를 최적화하여 가장 많은 라운드를 버틸 수 있도록 해야 한다.

---

문제 접근 방식 💡

• 우선순위 큐 (heapq)를 사용하여 가장 적은 병력의 적을 우선적으로 넘긴다.
• 현재 적이 기존에 넘긴 적 중 최소값(q[0])보다 크다면 교체한다.
• 병력(n)을 초과하여 소모하면 게임 종료.

---

Solution 💻

import heapq

def solution(n, k, enemy):
    answer = 0
    q = []
    
    for enem in enemy:
        if len(q) < k:
            heapq.heappush(q, enem)
        
        elif q[0] < enem and q[0] <= n:
            n -= heapq.heappop(q)
            heapq.heappush(q, enem)
        
        elif n >= enem:
            n -= enem
        
        else:
            break

        answer += 1

    return answer

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(m log k)
  • heapq 연산(push, pop)은 O(log k).
  • enemy 리스트 순회(m).
  • 따라서 전체 시간 복잡도는 O(m log k).

공간 복잡도 분석 🗄️

• 공간 복잡도: O(k)
  • heapq에 최대 k개의 요소만 저장.