알고리즘 코드카타 128 - 디펜스 게임

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 해주세요.

 

 

 

처음 풀어보는 방식의 문제라 접근방법에 대한 고민을 많이 했다. 처음 떠올린 방법은 k가 enemy의 길이보다 더 클 때(무적권이 라운드의 수보다 많을때) enemy의 길이를 반환하도록 예외처리를 하고 나머지 경우에 대해 계산을 하는 것이었다.

 

def solution(n, k, enemy):
    answer = 0
    l = len(enemy)
    
    if k >= l:
        return l
    
    for i in range(k+1, l+1):
        e = enemy[k:i]
        e.sort(reverse=True)
        if sum(e) > n:
            return len(e)+k

 

뭐 당연히...

 

처음으로 만들어본 알고리즘, 실패할 것은 예상했지만 생각 이상으로 많이 틀렸다. 로직이 맞지 않을뿐아니라 시간초과도 걸렸다. 아마 for문 안에 있는 sum때문일 것이다. 우선은 시간복잡도를 신경쓰지 않고 로직부터 완성해보도록하자.

위의 코드에서 잘못된 부분은  enemy를 슬라이싱하는 부분이다. k부터 슬라이싱을 시작한 의도는 미리 무적권을 사용한 뒤에 계산을 하려는 것이었지만 다시 생각해보니 정렬전에 무적권을 사용해버리면 최적화가 불가능했다.

 

def solution(n, k, enemy):
    answer = 0
    l = len(enemy)
    
    if k >= l:
        return l
    
    for i in range(k+1, l+1):
        e = enemy[:i]
        e.sort(reverse=True)
        e = e[k:]
        if sum(e) > n:
            return i-1

띠용

 

따라서 코드를 약간 수정해보았다. 대단한 수정을 한 것은 아니고 k로 슬라이싱하기 전(무적권을 사용하기 전)에 정렬을 먼저 해 주었다. 시간복잡도는 차차하더라도 아직도 실패가 나오는 것을 보니, 로직에 문제가 남아있는듯했다. 해결방법은 간단했는데 모든 무적권을 사용하고 남은 병사들로 남은 스테이지를 모두 클리어 했을때에 대한 예외처리가 되어있지 않았던 것이다. 

 

def solution(n, k, enemy):
    answer = 0
    l = len(enemy)
    
    for i in range(k+1, l+1):
        e = enemy[:i]
        e.sort(reverse=True)
        e = e[k:]
        if sum(e) > n:
            return i-1
    return l

 

간단하게 마지막에 return을 추가해서 해결을 했다. 자연스럽게 해당 코드와 중복이 되는 위쪽의 return은 삭제해주었다.

시간문제!

 

이제 풀이 방법 자체는 맞았다. 남은 것은 시간복잡도를 개선하는 것이다. 위에서도 설명했듯, 당연히 for문 안에 사용된 sum때문에 계산량이 과도하게 늘어났기 때문이다. 그래서 중복되는 계산을 제거해보기로 했다. 반복문마다 매번 sum을 새로 계산하는 것이 아니라 반복문이 시작될 때, 새로 추가될 값이 기존의 값중 가장 작은 값보다 더 작을 때, 굳이 값을 추가하지 않고 그 값을 n에서 빼주는 것이다. 이 방법으로 중복계산 되는 sum을 제거하고 현재 시점에서 가장 효율적인 선택을 반복할 수 있다.

 

입력값의 최소값을 반환하기 위해서 heapq를 사용한다.

 

import heapq

def solution(n, k, enemy):
    max_heap = []
    l = len(enemy)
    
    for i in range(l):
        heapq.heappush(max_heap, enemy[i])
        if len(max_heap) > k:
            n -= heapq.heappop(max_heap)
        if n < 0:
            return i

    return l

 

max_heap이라는 새로운 리스트를 생성해서 enemy의 원소들을 heap 규칙에 따라 순서대로 입력한다. 이때 , 입력된 원소들의 수가 k보다 더 크다면(무적권의 사용 범위를 초과한다면) 새로 추가된 값들중 가장 작은 값을 max_heap에서 제거한 후 그 값을 n에서 빼준다. 현재 시점에서 가장 작은 값을 뺀 것이므로 무적권들은 현재시점에서 가장 높은 값들에 사용되게 된다. 이때 n값이 0보다 작아진 경우에는 방어가 불가능한 상황이므로 현재 라운드의 번호를 반환한다.

 

드디어 성공

 

나중에 찾아보니 해당 문제는 그리디알고리즘에 대한 문제라고 한다. 부족한 개념을 하나 더 배운 느낌이다.