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

문제 링크

풀이

🥲 잘못된 접근

어마어마한 제한사항을 생각하지 못하고 사실상 거의 완전탐색에 가깝게 풀었다.

✔️ 길이를 한 칸씩 늘려가면서
✔️ 큰 수 부터 차례대로 k개를 제거한다(힙 사용)
✔️ 남은 합이 n보다 작은 경우 통과

그런데 가장 긴 길이를 찾는 거기 때문에 길이를 한 칸씩 늘리는 것보다 한 칸씩 줄이면서 확인하는 게 빠를 것 같았다. 그래서 그렇게 코드를 짜봤지만 시간초과...

😇 최종 풀이

핵심은 enemy의 길이가 무적권의 크기보다 작은 경우를 제외하면, 무조건 무적권의 길이보다 더 길어야 한다는 것이다. 즉 무적권을 다 사용하는 k길이 이상부터는 가장 작은 값부터 하나씩 n에서 빼면서 비교해주면 된다. 가장 작은 값부터 빼는 이유는 무적권을 사용해서 커버하게 되는 값들은 현재까지의 라운드에서 가장 큰 값들이기 때문. 가장 작은 값은 병사들을 사용해서 방어하고, 큰 값들은 무적권을 사용해서 방어한다.

이렇게 되면 하나씩 비교하는 완전탐색이 되면서 동시에 힙 자료구조를 사용하기 때문에 비교 시간이 logN으로 줄어들어 효율적인 비교를 할 수 있다.

✔️ enemy의 앞부터 힙에 하나씩 추가하면서
✔️ 길이가 k개 이상이 되면 가장 작은 값부터 하나씩 제거
✔️ 제거하면서 n에서 해당 값을 빼주는데
✔️ 이때 n의 값이 0보다 작아지면 라운드 종료

def solution(n, k, enemy):
    
    if len(enemy) <= k:
        return len(enemy)
    
    defense = []
    heapq.heapify(defense)
    for round, attack in enumerate(enemy):
        heapq.heappush(defense, attack)
        if round >= k:
            n -= heapq.heappop(defense)
            if n < 0:
                return round
    return len(enemy)
    
import heapq