[프로그래머스 알고리즘 스터디] 1주차 - 게임아이템

YUZAMIN
YUZAMIN
Hello, World! I'm YUZAMIN, a diligently endeavoring frontend developer 🐤💦
[프로그래머스 알고리즘 스터디] 1주차 - 게임아이템

Summary

문제 설명 📑

XX 게임의 유저들이 보스 몬스터를 사냥하려고 팀을 만들었습니다. 그리고 팀에 속한 캐릭터에 아이템을 사용해 공격력을 높이려 합니다. 이 게임의 아이템은 캐릭터의 공격력은 높이고 체력을 낮춥니다. 그래서 아이템을 적절히 사용해 팀의 공격력을 최대한 끌어올리려 합니다. 캐릭터별로 아이템을 사용할지 말지는 자유지만, 아이템을 사용한 캐릭터는 체력이 반드시 100 이상 남아야 합니다. 또, 한 캐릭터에 아이템 하나씩만 사용할 수 있으며, 사용한 아이템은 사라집니다. 예를 들어 캐릭터의 체력이 [200, 120, 150]이고 아이템의 효과는 다음과 같습니다. 이때 팀의 공격력을 최대로 올리려면 첫 번째 캐릭터에 첫 번째 아이템을, 세 번째 캐릭터에 두 번째 아이템을 사용하면 됩니다.

캐릭터들의 체력을 담은 배열 healths와 아이템별 효과를 담은 이차원 배열 items가 solution 함수의 매개변수로 주어질 때, 팀의 공격력을 최고로 끌어올리려면 어떤 아이템을 사용해야 하는지 return 하도록 solution 함수를 완성해주세요.

제한사항 🚫

healths의 길이는 1 이상 10,000 이하입니다. healths의 원소(캐릭터의 체력)는 1 이상 1,000,000 이하인 자연수입니다. items의 길이는 1 이상 5,000 이하입니다. items에는 아이템이 [올려줄 공격력, 낮출 체력]이 번호 순서대로 들어있습니다. 아이템 번호는 1번 부터 시작합니다. items[i]에는 i + 1번 아이템이 [올려줄 공격력, 낮출 체력]이 들어있습니다. 아이템이 올리는 공격력은 1 이상 500,000 이하인 자연수입니다. 아이템이 내리는 체력은 1 이상 500,000 이하인 자연수입니다. 아이템 번호는 오름차순으로 정렬해 return 해주세요. 올려주는 공격력이 같은 아이템은 없습니다. 아이템을 사용하는 방법이 여러 가지라면, 그러한 방법 중 아무거나 하나를 return 해주세요. 단, 아이템 번호는 오름차순으로 정렬되어 있어야 합니다.

문제 풀이 👩🏻‍💻

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# 게임아이템
import heapq
from collections import deque as queue


def solution(healths, items):
    answer = []
    # 체력이 낮은 캐릭터부터 아이템을 견주어볼 것이므로
    # 캐릭터의 체력을 오름차순으로 정렬
    healths.sort()

    items_index_heap = []

    # 아이템 배열을 순회하며 아이템 별 (감소되는 체력, 공격력, 해당 아이템의 인덱스) 튜플을
    # items_with_index 큐에 삽입
    items_with_index = queue(sorted([(reduced_health, attack, index)
                             for index, (attack, reduced_health) in enumerate(items)]))

    # 캐릭터 체력을 순서대로 순회
    for health in healths:
        # items_with_index 큐에 요소가 남지 않을 때까지 반복
        while items_with_index:
            # items_with_index 큐의 가장 처음 요소(감소되는 체력 양이 가장 작은 아이템)를
            # reduced_health에 할당
            reduced_health = items_with_index[0][0]

            # 선택된 캐릭터의 체력 health에서 reduced_health을 뺀 값이 100보다 작으면
            # break로 while문 탈출하여 if items_index_heap:으로 이동
            if health - reduced_health < 100:
                break

            # 선택된 캐릭터의 체력 health에서 reduced_health을 뺀 값이 100보다 크거나 같으면
            # 해당 아이템을 큐에서 pop
            _, attack, index = items_with_index.popleft()

            # 캐릭터가 장착할 수 있는 아이템들(items_index_heap) 중 공격력이 가장 높은 것을 장착시켜야 하므로
            # 공격력 기준 내림차순으로 index에 1을 더한 값을 heap에 삽입
            heapq.heappush(items_index_heap, (-attack, index + 1))

        # break로 while문을 탈출했을 경우
        # 만약 items_index_heap에 요소가 있을 경우
        # 즉, 캐릭터가 장착할 수 있는 아이템이 있는 경우
        if items_index_heap:
            # 가장 첫번째 요소, 즉, 그 중 가장 공격력이 높은 아이템의 index를 answer에 추가
            answer.append(heapq.heappop(items_index_heap)[1])

    return sorted(answer)

문제 출처