프로그래머스 디펜스 게임

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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 해주세요.

입출력 예

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]

입출력 예 설명

입출력 예#1

• 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.

입출력 예#2

• 준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.

풀이

• 이거 enemy 하나씩 무적권으로 처리하면서,
• 더 이상 무적권이 없으면 새로 나타나는 적과 무적권으로 죽인 가장 작은 적의 숫자를 비교해서 교환하고
• n으로 enemy를 처리. n이 여유가 있으면 반복.
• 무적권으로 죽인 적의 숫자를 힙큐로 만들면 되겠네?

import heapq

def solution(n, k, enemy):
    answer = 0
    무적권사용 = []
    for e in enemy:
        heapq.heappush(무적권사용, e)
        k -= 1 #무적권 수량감소
        
        if k <= 0: #무적권이 없으면
        	if n < e: #병사 수 체크
                break #병사가 모잘라서 종료
            if n > 무적권사용[0]: 병사수가 이전에 무적권을 사용한 것보다 많으면 무적권 취소
            	n -= heapq.heappop(무적권사용) #무적권 사용 취소
            	k += 1
                
        answer += 1
    return answer

• 안되네? ㅋㅋㅋ
• 다시 생각해보다가 안되서, 일단 enemy를 잘라서 무적권을 다 쓴 상태로 만들고 시작했다.
• 그리고 n이 0이면 병사가 0이라서 끝난걸텐데
  • if n<= 0: break 했더니 에러난다.
  • if n<0: break 했더니 통과되었다.
    • 문제 오류 아닌가?
    • 이게 병사가 0이 되어도 적을 다 죽였으면 다음 스테이지로 이동하는 방식으로 이해해야 하는 듯.
    • 진짜 게임이면 유저들이 말도 안된다고 버그라고 했을 듯...
    • 이거 때문에 1시간 넘게 고생해서 ... 오늘도 12시 넘겨서 잠든다. 쿨럭

import heapq

def solution(n, k, enemy):
    if len(enemy) <= k:
        return len(enemy)
    
    무적권 = []
    for i in range(k):
        heapq.heappush(무적권, enemy[i])
    
    del enemy[:k]
    
    스테이지 = k
    for 적 in enemy:
        #print(무적권, 스테이지, 적)
        if 무적권[0] < 적: #적이 더 작은지 무적권으로 죽인 적이 더 작은지 비교
            n -= heapq.heappop(무적권) #병사수 차감
            heapq.heappush(무적권, 적) #무적권 사용
        else: #적이 더 적으면
            n -= 적 #병사수 차감
        if n < 0:
            break
        스테이지 += 1
        
    return 스테이지
    
정확성  테스트
테스트 1 〉	통과 (0.36ms, 10.7MB)
테스트 2 〉	통과 (1.64ms, 11.5MB)
테스트 3 〉	통과 (126.92ms, 43.2MB)
테스트 4 〉	통과 (3.86ms, 18.7MB)
테스트 5 〉	통과 (0.00ms, 10.6MB)
테스트 6 〉	통과 (107.05ms, 56.4MB)
테스트 7 〉	통과 (56.21ms, 50.4MB)
테스트 8 〉	통과 (22.18ms, 49.8MB)
테스트 9 〉	통과 (39.84ms, 49.6MB)
테스트 10 〉	통과 (126.04ms, 46.1MB)
테스트 11 〉	통과 (0.48ms, 18.8MB)
테스트 12 〉	통과 (1.35ms, 18.7MB)
테스트 13 〉	통과 (0.00ms, 10.4MB)
테스트 14 〉	통과 (0.00ms, 10.4MB)
테스트 15 〉	통과 (0.01ms, 10.4MB)
테스트 16 〉	통과 (0.01ms, 10.3MB)
테스트 17 〉	통과 (0.00ms, 10.5MB)
테스트 18 〉	통과 (0.00ms, 10.6MB)
테스트 19 〉	통과 (0.01ms, 10.3MB)
테스트 20 〉	통과 (0.00ms, 10.3MB)
테스트 21 〉	통과 (0.01ms, 10.4MB)
테스트 22 〉	통과 (0.00ms, 10.4MB)
테스트 23 〉	통과 (0.03ms, 10.3MB)
테스트 24 〉	통과 (0.02ms, 10.3MB)
테스트 25 〉	통과 (0.02ms, 10.4MB)
테스트 26 〉	통과 (0.03ms, 10.4MB)
테스트 27 〉	통과 (0.03ms, 10.4MB)
테스트 28 〉	통과 (0.01ms, 10.4MB)
테스트 29 〉	통과 (0.05ms, 10.5MB)
테스트 30 〉	통과 (0.04ms, 10.2MB)
테스트 31 〉	통과 (0.04ms, 10.5MB)
테스트 32 〉	통과 (0.03ms, 10.4MB)

• 아참 고수의 풀이...

import heapq as hq
def solution(n, k, enemy):
    q = enemy[:k]
    hq.heapify(q)
    for idx in range(k,len(enemy)):
        n -= hq.heappushpop(q,enemy[idx])
        if n < 0:
            return idx
    return len(enemy)
    
테스트 1 〉	통과 (0.22ms, 10.5MB)
테스트 2 〉	통과 (1.45ms, 11.3MB)
테스트 3 〉	통과 (113.59ms, 43MB)
테스트 4 〉	통과 (2.15ms, 18.7MB)
테스트 5 〉	통과 (0.39ms, 10.4MB)
테스트 6 〉	통과 (58.79ms, 53.1MB)
테스트 7 〉	통과 (49.78ms, 50.4MB)
테스트 8 〉	통과 (30.46ms, 49.4MB)
테스트 9 〉	통과 (41.98ms, 49.5MB)
테스트 10 〉	통과 (172.18ms, 46MB)
테스트 11 〉	통과 (0.01ms, 18.4MB)
테스트 12 〉	통과 (0.04ms, 18.7MB)
테스트 13 〉	통과 (0.00ms, 10.1MB)
테스트 14 〉	통과 (0.00ms, 10.2MB)
테스트 15 〉	통과 (0.00ms, 10.2MB)
테스트 16 〉	통과 (0.00ms, 10.2MB)
테스트 17 〉	통과 (0.00ms, 10.2MB)
테스트 18 〉	통과 (0.00ms, 10.2MB)
테스트 19 〉	통과 (0.00ms, 9.98MB)
테스트 20 〉	통과 (0.00ms, 10.2MB)
테스트 21 〉	통과 (0.00ms, 10.3MB)
테스트 22 〉	통과 (0.00ms, 10.1MB)
테스트 23 〉	통과 (0.02ms, 10.2MB)
테스트 24 〉	통과 (0.02ms, 10.1MB)
테스트 25 〉	통과 (0.02ms, 10.2MB)
테스트 26 〉	통과 (0.03ms, 10.3MB)
테스트 27 〉	통과 (0.05ms, 10.2MB)
테스트 28 〉	통과 (0.02ms, 10.2MB)
테스트 29 〉	통과 (0.03ms, 10.3MB)
테스트 30 〉	통과 (0.01ms, 10.1MB)
테스트 31 〉	통과 (0.06ms, 10.2MB)
테스트 32 〉	통과 (0.02ms, 10.1MB)