[프로그래머스] LV.2 디펜스 게임 / 파이썬(Python)

 

📜 문제 설명

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

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

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

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

 

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

 

입출력 예

 

🔗 문제 링크

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

프로그래머스

 

💡 문제 풀이

이 문제를 보고 처음에 한 생각은 단순했다. 

디펜스 게임의 목적은 최대한 멀리 가는 것이다. 그래서 0번 인덱스 부터 출발해서 최대한 멀리가다가 적군의 수가 준호가 가진 병사 n을 넘어버리면 가장 적군의 머릿수가 많은 라운드에서 무적권을 사용한다. 

이 로직을 sum, sort, pop을 이용해서 구현했다. 

그랬더니 로직 자체는 틀리지 않은 듯 하지만 32개 중에서 6개 케이스에서 시간 초과가 발생했다. 

리스트 관련 메소드에서 시간 초과가 발생할 때는 heap을 쓰면 항상 옳다는 결론을 이전 문제들에서 많이 배웠다.

그래서 이 문제도 다시 heap을 사용했고 통과할 수 있었다.

def solution(n, k, enemy):
    answer = 0
    tmp_enemy = []
    
    for i in range(len(enemy)):
        tmp_enemy.append(enemy[i])
        tmp_enemy.sort()
        if i == len(enemy) - 1 and (k > 0 or sum(tmp_enemy) <= n):
            answer = i + 1
        if sum(tmp_enemy) > n and k > 0:
            tmp_enemy.pop(-1)
            k -= 1
        elif sum(tmp_enemy) > n:
            answer = i
            break
        else:
            continue
        
    return answer

 

heap을 사용했다는 것 외에 구현한 로직은 위의 로직과 동일하다. 

(0번 인덱스 부터 출발해서 최대한 멀리가다가 적군의 수가 준호가 가진 병사 n을 넘어버리면 가장 적군의 머릿수가 많은 라운드에서 무적권을 사용한다)

heap은 자동으로 정렬해줘서 정렬, 최대값을 찾는 시간을 많이 절약해준다. 다만 heap의 특성 상 기본적으로 오름차순 정렬이 되기 때문에 최대 힙을 구현하기 위해 힙에 값을 넣을 때 마다 앞에 -값을 넣어 주었다.

import heapq

def solution(n, k, enemy):
    i = 0
    tmp_sum = 0
    tmp_enemy = []
    heapq.heapify(tmp_enemy)
    
    while i < len(enemy):
        heapq.heappush(tmp_enemy, (-enemy[i], enemy[i]))
        tmp_sum += enemy[i]       
        
        if tmp_sum > n and k > 0:
            tmp_sum -= tmp_enemy[0][1]
            heapq.heappop(tmp_enemy)
            k -= 1
        elif tmp_sum > n and k == 0:
            break
        
        i += 1 
        
    return i

 

이 문제는 문제를 구현할 수 있는 로직 자체는 상당히 단순했다. 최대한 멀리 가다가 나 보다 적군의 힘이 세질 때 적군의 힘이 제일 강했던 라운드를 무효화하는 것이다. 다만 구현도 단순하게 하면 무조건 시간 초과가 발생하게 되어 있는 듯하다. 이럴 때 힙만큼 단순하지만 시간이 절약되는 게 없다.힙 진짜 효자

나의 힙 사랑은 예전 문제 풀이에서 부터 찾아볼 수 있다. 아래 링크는 레벨 3 문제도 힙을 사용해서 효율성을 잡았던 경우이다. 

https://honeynyancat.tistory.com/9

[프로그래머스] LV.3 숫자게임 / 파이썬(Python)