[자료구조] 게임 아이템 파이썬 (heap, deque)

해답

from heapq import heapify, heappush, heappop
from collections import deque

def solution(healths, items):
    healths.sort() # 체력을 오름차순으로 정렬
    items = sorted([(item[1], item[0], index+1) for index, item in enumerate(items)]) # 깎는 체력 순으로 정렬
    items = deque(items)
    answer = []
    heap = []

    for health in healths: # 제일 작은 체력부터 루프
        while items: # 아이템 루프
            debuff, buff, index = items[0] # 가장 깎는 체력이 낮은 아이템
            if health - debuff < 100: # 조건이 안맞으면 루프 종료
                break
            items.popleft() # 어차피 다음 체력에선 무조건 가능하기 때문에 이 시점에서 제거합니다. 여기서 deque를 사용해도 되겠죠?
            heappush(heap, (-buff, index)) # 힙에 추가합니다
        if heap: # 힙이 비어있지 않으면
            _, index = heappop(heap)
            answer.append(index) # 답 리스트에 추가합니다.

    return sorted(answer)

 

heap을 사용해서 빠른 처리가 가능하도록.

 

items를 sorted 함수에 넣는다.

여기서 sort 우선순위를 item[1], item[0], index+1 순으로 설정한다

tuple로 이 세가지를 묶음으로써 tuple이라는 iterable한 객체를 sorted의 인자로 넣어주는 것이다.

그 다음은 deque를 사용해서 heap에 넣을 준비를 한다.

 

while 문은 이미 sorted 된 healths 와 items를 체크하기 때문에

items[0] 의 element들을 선언하고

if 문으로 문제의 exit 조건에 해당하는 조건문을 넣어준다.

exit 조건이 아닐경우 (if문 통과)

popleft 해줘서 items에 있는 다른 tuple들을 계속 탐색하게끔 만든다

heap에는 heap과 heap에 들어갈 요소들을 tuple 형식으로 넣어준다.

여기서 최대 힙을 만들기 위해 tuple의 첫번째 원소에 minus를 해준다.

여기서 -buff 와 함께 index를 넣어주는데

문제에서 출력하고자 하는 값이 index이기 때문에 함께 넣어주는 것.

 

while문이 다 끝나면(items의 모든 element를 다 체크 함)

heap에 있는 모든 items를 heappop으로 꺼내서

index만 answer list에 append