[python] 프로그래머스 - 게임아이템

문제 설명

각 캐릭터는 보스몹을 잡기 위해 아이템을 사용해서 공격력을 높일 수 있음. 아이템을 사용하면 공격력이 올라가는 대신 체력이 감소함. 캐릭터는 아이템을 사용해서 공격력을 증가시키되 최소 체력은 100 이상을 유지해야 함. 이 상황에서 팀 내 공격력을 최대화하기 위해 사용 가능한 아이템 수를 구하여라.

입력

입력으로는 1) 각 캐릭터의 잔여 체력, 2) 아이템을 사용하며 증가하는 공격력 & 소모되는 체력 이 주어짐.

e.g.) healths = [100,200,300] // items = [[30, 20], [100, 50]]

제한 사항

1. healths의 길이는 1 이상 10,000 이하
2. healths의 원소는 1이상 1,000,000 이하인 자연수
3. items의 길이는 1 이상 5,000 이하
4. 아이템이 올리는 공격력과 아이템이 내리는 체력은 각각 1이상 500,000 이하인 자연수
5. 아이템 번호는 1번부터 시작하며 반환하는 정답값은 오름차순으로 정렬해야함.
6. 올려주는 공격력이 같은 아이템은 없다.
7. 아이템은 한 번 사용하면 소멸된다.
8. 한 사람 당 아이템을 사용할 수 있는 최대 횟수는 1번이다.
9. 아이템을 사용하는 방법이 여러 가지일 수 있으나, 그 중 하나만 반환하면 된다.

---

문제 풀이

로직

팀 내 공격력을 최대화하기 위해선 최대한 많은 캐릭터가 아이템을 사용해야 한다. 또한 조건에 부합하는 여러 아이템이 있을 경우, 높은 공격력의 아이템을 사용해야 한다. 즉 문제 풀이 시 고려해야 하는 사항은 체력 제한 조건 부합 여부와 아이템의 공격력 최대화이다.

체력 제한 조건이 있기 때문에 가장 적은 체력의 캐릭터가 아이템을 사용할 수 있는지에 대해서 판단해야 한다. 또한, 아이템을 사용하되 공격력이 높은 아이템부터 탐색을 함으로써 조건에 부합하는 아이템을 answer에 추가해주고, 해당 아이템(혹은 캐릭터)에 대해서 이미 아이템 사용이 끝났음을 표시한다.

코드

위 로직을 구현한 코드는 아래와 같다. 입력으로 받는 healths와 items를 각각 체력과 공격력을 기준으로 정렬해준다. 이때 items는 내림차순 정렬을 수행한다. nested loop을 돌면서 아이템 사용 가능 여부를 판단한다. outer loop의 기준이 캐릭터인지 아이템인지는 무관하다. 미리 말하자면 이 코드는 비효율적인 코드이다.

# 정렬 풀이
def solution_no_heap(healths, items):
    """
    health의 최소 요구치를 채우면서 아이템 사용을 통해 공격력을 최대화하라.
    아이템의 인덱스는 1-based index
    아이템은 일회용이고, 한 캐릭터는 딱 하나의 아이템만 사용 가능.
    """
    answer = []
    n, m = len(healths), len(items)
    n_rot = 0

    # item sort
    items = sorted(enumerate(items), key = lambda x: x[1][0], reverse = True) 
    healths.sort()

    # items에서 max값부터 비교하고 그 다음에 healths는 작은 값부터 비교해줌.
    for h_idx in range(n):
        for i_idx in range(m):
            n_rot += 1
            if len(answer) == m:
                return sorted(answer)
            if items[i_idx] == None:
                continue

            if (healths[h_idx] - items[i_idx][1][1]) >= 100:
                answer.append(items[i_idx][0]+1)
                #healths[h_idx] = -1
                items[i_idx] = None
                break

    print(n_rot)
    return sorted(answer)

이 경우에는 이미 모든 캐릭터들이 아이템 사용이 완료된 경우에도 혹은 아이템 사용이 불가능한 경우에 대해 확인이 완료되었을 때도 무조건 배열 탐색을 다 수행할 수밖에 없다. 따라서 이 부분에 대해서는 조건문으로 아이템 사용이 완료가 되었는지를 판별하여 미리 early stopping을 걸어줘야 효율성 테스트를 통과할 수 있었다.

그럼에도 불구하고 앞서 말했듯 이 코드는 매우 비효율적인 코드이다. 위의 코드에서 문제가 되는 점은 탐색 시 비효율성이 초래된다는 점이다. 실제로 배열을 정렬해서 탐색하는 데에는 탐색의 효율성을 위한 부분도 있다. 이미 앞에서 조건에 부합하지 않는다면(혹은 부합한다면) 뒤에서도 조건에 부합하지 않는다 (혹은 부합한다)등이 성립되기 때문이다.

하지만 위의 로직의 경우에는 정렬은 탐색 효율성 측면에서는 전혀 이득이 없다 (무조건 $n*m$의 시간복잡도를 가질 수밖에 없음).
아이템은 공격력을 기준으로, 캐릭터는 체력을 기준으로 정렬이 되었기 때문이다. 따라서 효율성을 제고하기 위해서는 둘 다 체력으로 정렬을 해주고 공격력 최대치를 찾아내기 위한 부분을 하나 더 추가해줘야한다.

추가되어야 할 부분은 조건에 맞는 애들을 따로 담아주고, 매번 새로운 원소가 삽입될 때마다 정렬을 해주며 각 캐릭터 별로 사용할 아이템을 최종적으로 answer에 append해주는 형식이다. 이 부분은 정렬을 명시적으로 해주지 않아도 rough한 정렬 상태가 유지되는 (max) heap을 통해 쉽게 구현이 가능하다.

---

효율적인 풀이

로직

문제는 체력 조건이 부합하는 아이템 중에서 최대의 공격력을 갖는 아이템을 찾아내는 걸 요구하고 있다. 따라서 문제를 쪼개서 본다면 1) 체력 조건이 부합하는지 체크 2) 해당 아이템 중 최대의 공격력을 갖게 할 것 으로 크게 2가지의 요구사항으로 정리할 수 있다.

이에 1)은 healths와 items를 모두 체력 순으로 정렬하여 불필요한 조건 부합 여부 체크를 방지한다. 또한 2)의 경우에는 1)에서 확인된 체력 조건에 부합하는 아이템 중 공격력의 최대치를 리턴해주는 것이다. 이때 공격력의 최대치는 각 캐릭터별로 리턴을 해주어야 한다.

코드

위의 로직을 코드로 구현하면 다음과 같다.

## 효율적인 방법

from collections import deque
from heapq import heappush, heappop

def solution_heap(healths, items):
    answer = []

    healths.sort()
    items = deque(sorted([item[1], item[0], idx+1] for idx, item in enumerate(items)))
    heap = []

    for health in healths: # 적은 체력의 캐릭터부터 탐색
        while items: # 소모하는 체력이 적은 아이템부터 탐색
            debuff, buff, idx = items[0]
            if health - debuff < 100: # 해당 아이템이 조건에 부합하지 않으면 더이상 아이템에 대한 탐색은 무의미하므로 다음 캐릭터로 넘어감.
                break
            else: # 해당 캐릭터가 해당 아이템 사용이 가능한 경우 (최소 체력 조건에 부합)
                items.popleft() # 이후의 캐릭터에서 해당 아이템에 대한 탐색을 할 필요가 없음 (무조건 조건에 부합할 수밖에 없기 때문에)
                heappush(heap, [-buff, idx]) # max heap

        if heap: # 해당 캐릭터가 사용 가능한 아이템이 존재할 경우
            _, idx = heappop(heap) # max heap에서 공격력이 최대인 아이템을 answer에 삽입함.
            answer.append(idx)

    return sorted(answer)

유의할 점은 캐릭터 별로 최대 공격력을 갖는 아이템을 answer에 삽입해줘야하며, 일괄적으로 나중에 적용하는 것은 불가능하다는 점이다. 일괄적으로 나중에 적용하게 되면 체력이 낮은 경우에는 맞지 않는 조건의 아이템이 answer에 포함이 될 수 있기 때문이다. 또한 이 경우에는 각 item에 여러번 접근을 하면서 조건에 맞는 item을 탐색을 해야하므로 outer loop이 무조건 캐릭터를 기준으로 해야한다.

---

정리

heap을 어떻게 사용할지에 대해 조금 더 고찰할 수 있었고, 정렬을 통해 탐색을 효율적으로 가져가는 로직에 대해 보다 더 고려할 수 있었던 문제였다. 또한 문제 분석과 문제를 어떻게 쪼개서 생각하느냐가 중요하다는 걸 다시금 되새길 수 있었다.