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

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

프로그래머스

해설

게임을 하다 죽었다고 치자. 죽었을 때 과거의 적들중 가장 값이 큰값에 k를 소모하면 더 오래 게임하지 않을까?

 

알고리즘 과정은 다음과 같다

• while문을 돌리면서 게임을 한다
• 게임을 하다가 죽으면 이전 적들중 가장 큰 값에 k를 사용한다 => 이전적들은 heapq로 저장하면 가장 큰놈을 찾을 수 있다

 

 

내가 실수한점

k는 죽었을 때 한번만 써야 하는데, 죽었을 때 k를 while문으로 전부다 쓰려고 했음

 

from collections import *
import heapq
def solution(n, k, enemy):
    answer = 0
    dq = deque(enemy)
    hq = []
    while n>=0 and dq:
        pop = dq.popleft()
        n-=pop
        heapq.heappush(hq,-pop)
        if n >= 0:
            answer+=1
        elif k>0:
            n-=heapq.heappop(hq)
            k-=1
            answer +=1

    return answer

 

 

 

 

다른 방법

• k를 가장 큰놈들에게만 사용하면 된다
• 그러면 k에 들어갈 애들은 heapq에 enemy를 k개만 담은 뒤 가장 작은놈들만 빼내는 식으로 관리하면 게임을 오래 할 수 있다.

from collections import *
import heapq
def solution(n, k, enemy):
    answer = 0
    klist = enemy[:k]
    heapq.heapify(klist)
    for i in range(k, len(enemy)):
        n -= heapq.heappushpop(klist,enemy[i])
        if n <0:
            return i
    return len(enemy)