[프로그래머스-디펜스 게임] (Python)

문제

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

프로그래머스

문제 해결 아이디어

• 무적권은 우선적으로 사용한다 
• 단, 앞에서부터 살펴보면서 해당 위치까지 가장 큰 스테이지부터 무적권 사용해야 함 
  -> 무적권을 사용한 스테이지 중, 적의 수가 가장 작은 스테이지보다 현재 적의 수가 더 많으면 무적권을 현재 스테이지에 사용 
  -> 힙 구조를 이용해야겠다 

문제풀이

1. 앞 스테이지부터 탐색, 사용한 무적권이 k보다 적으면 무적권 무조건 사용 
2. 이미 k개의 무적권을 모두 사용한 경우, 해당 스테이의 적의 수가 무적권을 사용한 스테이지의 가장 작은 적의 수보다 크면 무적권 사용 변경, 이전에 사용한 무적권의 적의 수는 n-= 해줌
   - 무적권 무효하는 스테이지의 적의 수가 n 보다 작거나 같아야 함. 그렇지 않으면 종료 
3. 이미 k개의 무적권을 모두 사용한 경우, 해당 스테이지의 적의 수가 무적권을 사용한 스테이지의 가장 작은 적의 수보다 작거나 같은 경우, 무적권 변경 x, 
   - 현재 스테이지의 적의 수가 n 보다 작거나 같은 경우만 클리어 가능, 그렇지 않으면 종료 

코드 

import heapq 
def solution(n, k, enemy):
    answer = len(enemy)
    
    hq = []
    for i in range(len(enemy)):
        if len(hq) < k:
            heapq.heappush(hq, enemy[i])
            continue
        if hq[0] >= enemy[i]:#무적권 사용 바꿀 수 없음 
            if n< enemy[i]:
                return i
            else: 
                n -= enemy[i]
                continue 
        elif hq[0] < enemy[i]: #무적권 사용 바꾸기 
            if n>= hq[0]: 
                n -= heapq.heappop(hq)
                heapq.heappush(hq, enemy[i])
            else:
                return i #i 스테이지 막을 수 없음 
    
    return answer