프로그래머스 - 디펜스 게임

문제 링크 ▶︎ 프로그래머스 디펜스 게임

문제 전략

이 문제는 힙으로 구현한 문제이다.

매 라운드 공격해오는 적의 수를 최대힙으로 받아서, 합산한 값이 n 보다 커지게 되면 가장 큰 값을 pop하고 k -= 1 해준다.
줄어든 합산 값으로 계속 진행한다.

만약, enemy 배열을 다 돌았는데 합산 값이 n 보다 크다면 그 배열 길이가 정답이 된다.
그리고 합산 값이 n 보다도 작은 순간에 만약 k 를 다 썻다면 그 index 가 정답이고 k가 남아있다면 다음 index가 정답이 된다.

코드

from heapq import heappop, heappush
def solution(n, k, enemy):
    answer = 0
    h = []

    for i,v in enumerate(enemy):
        n -= v
        heappush(h,(-1*v))
        
        if n < 0 :
            if k > 0:
                chance = -heappop(h)
                n += chance 
                k -= 1
                answer = i+1
            else:
                answer = i 
                break
        else:
            answer = i+1 
            
    return answer

개선 사항

처음에 bfs로 visit을 enemy 배열을 k개 붙여서 2차원 배열로 만들어서 방문하며 구현해봤지만 시간 초과가 발생해서 시간을 줄일 방법을 고민해봐야 할듯.