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

문제 링크:

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

회고:

• 문제 풀이 방법 간단 정리
  • enemy 리스트에서 k갯수만큼 순차적으로 힙리스트(=아래 소스코드 queue 참고)에 담는다.
  • enemy에서 앞의 k갯수 제외한 나머지에 대해 순차적으로 하나씩 가져오는데, queue에 담긴 값중 최솟값보다 더 크다면 queue의 최솟값을 제거하고 enemy에서 가져온 값을 queue에 추가한다.
  • 이렇게 하는 이유는 무적권을 가급적 적의 수가 많을 때 사용하기 위함이다.
    
    

python

# n: 처음 갖고 있는 병사 수, k: 무적권 횟수, enemy: 매 라운드마다 공격해오는 적의 수 리스트
# 최대 몇 라운드까지 막을 수 있는지 리턴

from heapq import heappop, heappush


def solution(n, k, enemy):
    if k >= len(enemy):
        return len(enemy)

    round = 0

    queue = []
    for i in range(k):
        heappush(queue, enemy[i])

    for num in enemy[k:]:
        if queue[0] < num:
            if n >= queue[0]:
                n -= heappop(queue)
                heappush(queue, num)
                round += 1
            else:
                break
        else:
            if n >= num:
                n -= num
                round += 1
            else:
                break

    round += k
    return round


if __name__ == "__main__":
    result = solution(7, 3, [4, 2, 4, 5, 3, 3, 1])

    print(result)

5