최소 힙을 음수화 해서 최대 힙으로 사용하는 문제
빈번한 최대값 도출
문제설명
이 게임의 아이템은 캐릭터의 공격력은 높이고 체력을 낮춥니다. 그래서 아이템을 적절히 사용해 팀의 공격력을 최대한 끌어올리려 합니다. 캐릭터별로 아이템을 사용할지 말지는 자유지만, 아이템을 사용한 캐릭터는 체력이 반드시 100 이상 남아야 합니다. 또, 한 캐릭터에 아이템 하나씩만 사용할 수 있으며, 사용한 아이템은 사라집니다.
캐릭터들의 체력을 담은 배열 healths와 아이템별 효과를 담은 이차원 배열 items가 solution 함수의 매개변수로 주어질 때, 팀의 공격력을 최고로 끌어올리려면 어떤 아이템을 사용해야 하는지 return 하도록 solution 함수를 완성해주세요.
입출력 예
예를 들어 캐릭터의 체력이 [200, 120, 150]이고 아이템의 효과는 다음과 같습니다.
높여줄 공격치 낮추는 체력
30 100
500 30
100 400
이때 팀의 공격력을 최대로 올리려면 첫 번째 캐릭터에 첫 번째 아이템을, 세 번째 캐릭터에 두 번째 아이템을 사용하면 됩니다.healths items return [200,120,150] [[30,100],[500,30],[100,400]] [1,2] [300,200,500] [[1000, 600], [400, 500], [300, 100]] [3]
솔루션
아이템은 인덱스 값과 함께 저장한 후 체력을 깎는 양이 적은 수부터 꺼낼 수 있게 정렬한다.
체력이 낮은 캐릭터 순으로 정렬한 후 cand에 이 캐릭터가 쓸 수 있는 아이템들을 공격력에-값을 붙여 넣어준다.
쓸수 있는 아이템 리스트(cand)가 있다면 그중에서 가장 공격력이 큰 아이템을 heappop해주고 idx를 answer에 저장하는 과정을 반복해준다.
코드
# 파이썬
import heapq
from collections import deque
def solution(healths, items):
healths.sort()
items = [(*item,index) for index, item in enumerate(items, 1)]
ATTACK, HP, IDX = 0, 1, 2
items = deque(sorted(items, key=lambda x:x[HP]))
answer = []
cand = []
for health in healths:
while items and health - items[0][HP] >= 100:
item = items.popleft()
heapq.heappush(cand, (-item[ATTACK], item[IDX]))
if cand:
answer.append(heapq.heappop(cand)[1])
return sorted(answer)팁
python의 heapq는 min heap이기 때문에 max heap으로 사용할 시 -값을 붙여주어 사용한다.
