디펜스 게임 (우선순위큐, 힙)

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

프로그래머스

 

분석

통과 못하는 시점의 인덱스 = 몇 라운드까지 막을 수 있는지

병사의 수 n=7
사용 가능한 무적권의 횟수 k = 3
라운드마다 공격해오는 적의 수 enemy = [4, 2, 4, 5, 3, 3, 1]

인덱스	힙	병사수
0	[4]	7
1	[2, 4]	7
2	[2, 4, 4]	7
3	[2, 4, 4, 5] (한 라운드 무적권 사용불가하므로 병사 수 계산)	5
4	[2, 3, 4, 5, 4] (한 라운드 무적권 사용불가하므로 병사 수 계산)	5
5	[2, 3, 3, 4, 5, 4] (한 라운드 무적권 사용불가하므로 병사 수 계산)	2

무적권 사용 안되는 라운드 병사 수 계산해서 -1 나오면 인덱스 리턴

풀이

from heapq import heappush, heappop
def solution(n, k, enemy):
	
    h = []
    for i, e in enumerate(enemy):
        heappush(h, e)
        if len(h)>k: # 무적권 사용 불가 라운드 병사수 계산
            n -= heappop(h)
        if n<0:
            return i

    return len(enemy) # 모든 라운드 무적권 사용