On.

---

Algorithm

---

1. 수도코드

1) healths를 오름차순으로 정렬한다.

2) items를 (debuff, buff, index)순으로 재정비하고, 오름차순으로 정렬하여 deque로 만든다.

3) healths를 기준으로 순회한다. (for문)

4) while 문으로 items에 원소가 전부 사라질 때 까지 순회한다.

5) debuff, buff, idx = items[0]으로 미리 제일 적은 디버프를 가진 아이템을 준비해놓는다.

6) 제일 적은 체력의 캐릭터가 items 중 제일 적은 debuff를 받고도 체력이 100이 남지 않는다면 break로 중단한다.

7) 체력이 100이상 남았으면, items에서 pop을 하여 해당 아이템을 삭제시키고 기존에 할당해 두었던 buff와 idx로 select 리스트에 (-buff, idx) 형태로 heappush 한다. (맥스힙)

8) items에 원소가 다 빠져서 while문이 끝나면 select에 원소가 있는지 확인

9) 있으면 select에서 heappop한다.

10) pop해서 나온 idx를 answer에 append 시킨다.

11) sort시킨 answer를 리턴한다.

2. 구현코드

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

def solution(healths, items):
    answer=[]
    healths.sort()
    items = deque(sorted([(item[1], item[0], idx + 1)for idx, item in enumerate(items)]))
    select = []
    
    for h in healths:
        while items:
            debuff, buff, idx = items[0]
            if h - debuff < 100:
                break
            items.popleft()
            heappush(select, (-buff, idx))
        
        if select:
            _, idx = heappop(select)
            answer.append(idx)
    
    return sorted(answer)

3. 배운 점

• 배열에 있는 원소를 특정 조건에서 순서대로 제거해야하는 경우가 생기면, while로 돌면서 deque로 popleft() 시키는 방법이 있다.

• 짝지어서 순위를 매기거나 비교하는 경우에는 sorted나 sort를 사용하여 정렬하고 비교하는 것도 한 방법이다!

---

Off.

---

프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥