디펜스 게임

프로그래머스

 

쉽지 않았던 문제.

처음에는 이거 백트래킹으로 풀어야하나? 라는 생각이 들어서 백트래킹으로 코드를 한 번 작성해봤다.

 

---

첫 풀이 -> 백트래킹 사용 -> 오답 및 시간초과

 

import sys
sys.setrecursionlimit(10**6)

maxim = 0

def backTracking(n, k, enemy, answer):
    global maxim
    if n == 0:
        return answer
    if n < 0:
        return answer - 1
    if len(enemy) == 0:
        return answer
    
    # 무적권을 쓰지 않고 병사로 막는 경우
    maxim = max(backTracking(n-enemy[0], k, enemy[1:], answer + 1), maxim)
    n += enemy[0]
    answer -= 1
    # 무적권을 쓰는 경우
    maxim = max(backTracking(n, k-1, enemy[1:], answer + 1), maxim)
    
    return maxim


def solution(n, k, enemy):
    answer = 0
    
    if k >= len(enemy):
        return len(enemy)
    if n >= sum(enemy):
        return len(enemy)
    
    answer = backTracking(n, k, enemy, 0)
    return answer

 

시간초과 및 오답이 나오는 걸 보고 이건 아니다 라는 생각이 들었다.

그럼 도대체 어떤 자료구조나 알고리즘을 사용해서 풀어야할지 감이 잡히지 않았다.

순서대로 데이터를 받아야 하니까 라운드의 적수가 큰 수로 정렬해서 푸는 건 아니었고, 뭘 써야할 지 모르겠어서 풀이를 참고해서 풀었다.

 

---

풀이 코드 -> 우선순위 큐 사용

 

import heapq # 우선순위 큐 사용

def solution(n, k, enemy):
    answer = 0
    
    # 만약 사용가능한 무적권의 횟수가 전체 라운드 수 이상이거나, 준호가 처음 가지고 있는 병사의 수가 전체 적 수 이상이라면 모든 라운드를 막을 수 있으므로 enemy의 길이 리턴
    if k >= len(enemy) or n >= sum(enemy):
        return len(enemy)
    
    # 무적권의 횟수만큼 일단 우선순위 큐에 넣는다.
    q = enemy[:k]
    heapq.heapify(q)
    
    answer = k
    index = k
    
    # 준호가 가지고 있는 병사의 수가 0보다 큰 경우에 반복문을 돌린다.
    while n > 0:
        # 만약 index가 초과하는 경우는 모든 라운드를 막아낼 수 있는 경우이므로 answer를 리턴
        if index >= len(enemy):
            return answer
        
        # 큐에 들어 있던 한 라운드의 적 수에서 가장 작은 적 수인 q_min_enemy
        q_min_enemy = heapq.heappop(q)
        # 만약 현재 라운드의 적 수가 큐에 들어 있던 가장 적은 적수보다 크다면, 현재 라운드를 큐에 넣고(무적권을 사용), 큐에 들어 있던 가장 적은 적수는 준호의 병사로 막는다.
        if enemy[index] > q_min_enemy:
            heapq.heappush(q, enemy[index])
            n -= q_min_enemy
        # 반대라면 큐에 들어 있던 가장 적은 적수를 다시 큐에 넣고(무적권을 사용), 현재 라운드를 준호의 병사로 막는다.
        else:
            heapq.heappush(q, q_min_enemy)
            n -= enemy[index]
        
        # index, answer 추가
        index += 1
        answer += 1
        
    # 만약 n이 0이면 answer 리턴
    if n == 0:
        return answer
    # n이 0보다 작으면 그 전라운드 까지 막을 수 있는 것이므로 answer - 1 리턴
    else:
        return answer - 1

 

우선순위 큐를 사용해서 푸는 문제였다.

우선순위 큐에 k 길이 만큼의 각 라운드별 적수를 넣고, 앞에서부터 차례대로 라운드 별 적수를 확인하며 현재 확인하는 라운드별 적수보다 큐에 들어 있는 가장 적은 라운드별 적수가 작다면 현재 확인하는 라운드별 적수를 큐에 넣고, 원래 큐에 들어 있던 라운드별 가장 적은 적수는 준호가 가지고 있는 병사를 통해 처리해주면 된다.

---

 

우선순위 큐의 새로운 활용법을 알 수 있는 문제였다.