[Python] 프로그래머스 Lv 3 - 게임아이템

Heap을 활용하는 또 다른 문제

프로그래머스 Lv 3 게임아이템 풀이
출처 : 프로그래머스 스쿨

알고리즘

우선 포인트는 다음과 같다.

(1) 템 어차피 1개 밖에 못 낀다.
(2) 남이 못 낀 템, 내가 HP가 충분하면 먹을 수 있다.
(3) 그런데 먹을 수 있는 템 중에선 제일 좋은거를 껴야 한다.

따라서 다음 순서대로 푼다.
(1) 캐릭의 HP와 item을 정렬한다.
  (1)-1  이 때, item에는 체력, 공격력, index를 부여하는 새로운 item list를 만든다. enumerate를 활용하자. 
  (1)-2 다중리스트여도 별 조건 없으면 첫 성분의 오름차순 기준으로 정렬된다. 따라서 깎이는 HP를 맨앞에 쓴다.
(2) 캐릭별로 한명씩 item 착용을 시도한다. 이제 낮은 hp를 가진 사람은 hp가 덜 깎이는 애부터 찬다.
  이 때, 못 끼는게 나올때까진 다 시도해봐야 한다.
  낄 수 있는 item은 별도로 저장해두되, 공격력과 index를 같이 저장해둔다.
(3) 낄 수 있는 item 리스트에서 공격력이 제일 높은 애를 고르고 index만 반환한다.
(4) 그걸 다른 캐릭터에 적용한다. 나보다 피통이 낮은 애가 낄 수 있는건 나도 낀다.

이를 바탕으로 코드를 작성하면 다음과 같다.

코드

from collections import deque
import heapq
def solution(healths, items):
    answer = []
    healths.sort()
    idx_items = sorted([(item[1], item[0], idx) for idx, item in enumerate(items, 1)])
    idx_items = deque(idx_items)
    
    item_save = []
    heapq.heapify(item_save)
    
    for hp in healths:
        while idx_items:
            damage, attack, idx = idx_items[0]
            if hp-damage < 100:
                break
            idx_items.popleft()
            # 우선순위는 첫번째에 있다. 따라서 찰수 있는 것중 제일 쎈거 맥이기
            heapq.heappush(item_save, (-attack, idx))
        if item_save:
            _, idx = heapq.heappop(item_save)
            answer.append(idx)
            
    return sorted(answer)