디펜스 게임

 

 

코딩테스트 연습 - 디펜스 게임 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 코드

# 2024-04-18
def solution(n, k, enemy):
    answer = 0
    
    # 애초에 디펜스가 가능한경우 바로 return
    if k >= len(enemy):
        return len(enemy)
    
    # 라운드를 늘려가며 탐색
    for len_index in range(1, len(enemy)+1):
        new_enemy=enemy[:len_index]
        #print(new_enemy)
        for _ in range(k):
            if new_enemy:
                new_enemy.remove(max(new_enemy))
        if sum(new_enemy)>n:
            return answer
        answer+=1
    return answer

시간 초과 발생...

 

수정 코드

# 2024-04-18
import heapq
# 애초에 방어권이 충분한 경우 모든 라운드 return
def solution(n, k, enemy):
    if k>=len(enemy):
        return len(enemy)
    
    heap_queue=[]
    # 순차 탐색하며 heappop해주기
    for i in range(len(enemy)):
        heapq.heappush(heap_queue,enemy[i])
        if len(heap_queue)>k:
            n-=heapq.heappop(heap_queue)
        if n<0:
            return i
    return len(enemy)