[Python] 프로그래머스: 디펜스 게임

프로그래머스: 디펜스 게임

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

프로그래머스

문제 명세

문제 설명

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

문제 풀이

이 문제는 특정 스테이지를 클리어할 수 있는지 없는지를 판단하여 가장 멀리 간 경우의 수를 계산하는 문제입니다.

이를 계산하기 위해서는 두 가지 로직이 필요합니다.

 

1. 임의의 스테이지의 클리어 가능 여부 판단

2. 몇 번째 스테이지를 탐색할지 판단

 

첫 번째 로직부터 짜 보겠습니다.

 

임의의 n번째 스테이지가 클리어 가능한지 판단하기 위해서는 다음과 같은 로직이 필요합니다.

 

1. 1~n 번째 스테이지의 숫자들을 모은다.

2. 모은 숫자들을 정렬한다.

3. k개까지 가장 큰 숫자들을 제외하고 합한다.

4. 합한 수가 내 병사 수보다 크면 실패, 합한 수보다 내 병사 수가 크거나 같으면 성공이다.

 

두 번째 로직을 짜 보겠습니다.

 

제한사항 세 번째에 다음과 같은 내용이 있습니다.

• 1 ≤ enemy의 길이 ≤ 1,000,000

enemy의 길이를 고려했을 때, 스테이지 클리어 가능을 모두 탐색하면 시간 효율성에서 통과하지 못합니다.

이와 같이 연속된 숫자들 사이에서 내가 찾고 싶은 숫자를 빠르게 찾아야 할 경우 사용할 수 있는 유용한 알고리즘은 이진 탐색입니다.

따라서 첫 번째 로직을 이진 탐색을 적용하여 원하는 스테이지를 빠르게 찾는 것이 필요합니다.

 

두 가지 로직을 모두 적용하여 코드를 작성하면 다음과 같습니다.

def solution(n, k, enemy):
    
    left = 0
    right = len(enemy)

    while left <= right:
        mid = (left + right) // 2
        fight_range = enemy[:mid]
        enemy_to_fight = sum(sorted(fight_range)[:-k])
        if enemy_to_fight > n:
            right = mid - 1
        elif enemy_to_fight < n:
            left = mid + 1
        else:
            return mid

    return right