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

사이트 링크: https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

 

문제

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해 오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해 주세요.

 

입출력

 

 

제한사항

 

 

코드

import heapq

def solution(n, k, enemy):

    removes = []
    for i in range(len(enemy)):
        if len(removes) < k:
            heapq.heappush(removes, enemy[i])
        elif enemy[i] > removes[0]:
            n -= heapq.heappop(removes)
            heapq.heappush(removes, enemy[i])
        else:
            n -= enemy[i]
        if n < 0:
            i -=1   #n이 0보다 아래이면 i 보다 한인덱스 앞이 최선
            break
            
    answer = i+1    #인덱스 맞추기용
    return answer

 

문제풀이

저도 그랬지만 문제를 보자마자 단순 구현 문제로 먼저 풀었습니다.

max index를 업데이트하는 식으로 빡구현 하는 중간에 제한사항에 눈이 들어왔는데

바로 k가 최대 500,000이 될 수 있다는 제한이었습니다.

 

리스트에서 최솟값을 비교하면서 인자를 넣고 빼야 하는 건데 리스트의 길이가 500,000이며 n은 최대 1,000,000,000이었는데 이때 heap을 이용하여 푼다고 제한사항 만으로 파악하는 게 중요한 문제였던 것 같습니다.

 

구현 난이도는 낮았고 "제한사항만으로 heap을 사용한다는 걸 파악할 수 있는가?"를 중점적으로 보는 문제라 생각합니다.