[프로그래머스-lv2]디펜스 게임/파이썬

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

---

문제 풀이)

heap을 이용해 풀수 있었다.

문제 풀이 과정은 다음과 같다.

enenmy list의 원소들을 순서대로 탐색하며 다음과 같은 절차를 밟는다.

1) n(내가 보유하고 있는 병사수)가 enenmy[i](i번째 스테이지 적의 수) 수보다 많다면 내가 보유하고 있는 병사수에서 빼준다. 이러면 특정 스테이지에서 무조건 막히게 되있는데 이때 최대힙을 이용한다. 최대힙에서 heappop()을 하게 되면 내가 지나온 스테이지중 가장 많은 적의 수가 나오게 되있다. 힙에는 내가 스테이지를 클리어하며 소모된 병사의 수(=enemy수)가 저장되어 있다고 가정한다.

 

2) 이때 부터 내가 무적권의 수를 갖고 있다면, 다음의 절차를 따라 비교를 수행해준다.

 

    - 만약 힙의 최상단 원소가 enemy[i]의 값보다 크다면 이때는 무적권을 이용해 내가 지금까지 깨온 스테이지중 가장 적이 많았던 enemy를 갖고있던 스테이지를 클리어한다. 이유는 내가 보유하고 있는 병사의 수가 많을 수록 다음 스테이지를 깰 확률이 올라갈 것이기 때문이다. 이 때 a-enemy[i]만큼 다시n에 더해준후 해당 스테이지를 무적권을 이용해 갱신하고 enemy[i]는 다시 heap에 넣어준다. 왜냐면 저 차이만큼 나는 병사를 덜 소모하게 될것므로 이미 많이 썻던 스테이지를 무적권으로 클리어하고 그것보다 적은 병사를 필요로 했던 스테이지를 heap에 push해 준다.

 

    - 만약 힙의 최상단 원소가 enemy[i]보다 작다면 enemy[i]가 있는 스테이지를 무적권을 이용해 클리어한뒤 heap에 a값을 넣어준다.

 

위 과정을 무적권이 남아있을때까지 즉, k > 0일때까지 반복해 주면 된다.

 

전체 코드는 다음과 같다.

import heapq
def solution(n, k, enemy):
    heap = []
    if k == len(enemy):
        return len(enemy)
    for i in range(len(enemy)):
        if n >= enemy[i]:
            heapq.heappush(heap, -enemy[i])
            n -= enemy[i]
        else:
            if k > 0:
                if heap:
                    a = -heapq.heappop(heap)
                    k -= 1
                    if a > enemy[i]:
                        n += (a - enemy[i])
                        heapq.heappush(heap, -enemy[i])
                    elif a == enemy[i]:
                        heapq.heappush(heap, -enemy[i])
                    else:
                        heapq.heappush(heap, -a)
                else:
                    k -= 1
            else:
                return i
    return len(enemy)