프로그래머스 [Lv. 2] 디펜스 게임 {언어 : Python} [반례 포함]

문제 링크

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

프로그래머스

정답 코드

import heapq
def solution(n, k, enemy):
    answer = 0
    
    cntR = len(enemy)
    if cntR <= k:
        return cntR
    
    q = []
    for i in range(k):
        heapq.heappush(q, enemy[i])
        
    for j in range(k, cntR):
        nextV = enemy[j]
        front = q[0]
        answer = j
        if nextV > front:
            if front > n:
                break
            n -= heapq.heappop(q)
            heapq.heappush(q, nextV)
        else:
            if nextV > n:
                break
            else:
                n -= nextV
                
        if j == cntR - 1:
            answer += 1
    
    return answer

반례

Parameters     n = 4     k = 2     enemy = [2, 2, 100]

Return     3

풀이 방법

1. 무적권이 라운드 수보다 많으면 라운드 수를 반환한다.
2. q에 무적권의 개수만큼 enemy[i]를 push 한다.
3. k번째 인덱스부터 q의 첫 번째 (가장 작은 적의 수)와 다음 오는 enemy[j]와 비교한다.
   1. front 값이 작은 경우 무적권을 이번 라운드에 써야하므로 q에서 뺀다음 이번 nextV를 push 한다.
   2. 라운드를 거듭할 때마다 answer를 갱신하는데 반례와 같이 모든 라운드를 돌파하고 끝나는 경우 1이 모자라므로 +1을 해준다.
   3. 하지만 적의 수(front 또는 nextV) 보다 n이 작은 경우 직전 라운드는 통과했기 때문에 별다른 조치 없이 break를 해준다.
4. answer를 반환한다.

느낀점

• heap을 더 자유자재로 쓸 수 있도록 노력하자