[PRO] 디펜스 게임 | Python

문제

프로그래머스 코딩테스트 연습 > 연습문제 > 디펜스 게임 | Lv.2

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

프로그래머스

 

 

 

 

풀이 과정

파이썬 풀이

from heapq import heappop, heappush

def solution(n, k, enemy):
    if k >= len(enemy):
        return len(enemy)
    
    answer = 0
    num = 0
    hq = []
    
    for e in enemy:
        # heappop은 가장 작은 값을 제거하는데
        # e가 가장 클 때 무적권을 사용해야 하므로 음수로 저장 
        heappush(hq, -e)
        num += e
        if num > n:
            # 적의 수의 합이 n보다 큰데 무적권도 없으면 불가 -> break
            if not k:
                break
            # 남아있으면 heappop을 통해 해당 적의 수에 대해 무적권 사용
            k -= 1
            # 해당 수만큼 적이 없는 것이나 마찬가지이므로 num에서 다시 빼는데
            # 음수로 저장했으니까 더해줘야 함
            num += heappop(hq)
        answer += 1
    
    return answer

• 처음에 아래 풀이와 같이 무적권을 사용하는 경우와 사용하지 않는 경우로 나누어 재귀를 통해 풀이했는데, 2개의 테케는 통과했으나 많은 케이스에서 런타임 에러 혹은 시간초과가 났다.
  아마 재귀 호출 횟수 초과로 인해 런타임 에러가 나고, 시간 초과가 난 것 같다.
• 생각해보니 k가 최대 500,000이고 len(enemy)가 최대 1,000,000이므로 해당 방법으로는 안될 것 같다.
• 결국 질문하기와 구글링의 도움으로 풀이하였는데, 우선순위 큐를 오랜만에 썼더니 정확히 기억이 나지 않았다.
• 다음부터 시간복잡도를 먼저 고려하고, 어떤 로직을 사용해야 할지 더 많이 고민해봐야겠다.
• k가 enemy의 길이 이상이면 모든 라운드를 통과할 수 있으므로 바로 len(enemy)를 return

 

 

틀린 풀이 - 시간초과/런타임에러

def solution(n, k, enemy):
    l = len(enemy)
    if k >= l:
        return l
    
    answer = 0
    def dfs(num, idx, cnt, enemy):
        nonlocal answer, l
        if num < 0:
            return
        if idx + 1 == l:
            answer = l
            return
        answer = max(answer, idx)
        dfs(num - enemy[idx], idx+1, cnt, enemy)
        if cnt < k:
            dfs(num, idx+1, cnt+1, enemy)
            
    dfs(n, 0, 0, enemy)
    return answer