[프로그래머스](파이썬)-게임아이템-Level3-힙(heap)사용 문제

안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 게임아이템 문제를 풀어보겠습니다.

이 문제는 사실 그냥 List로도 풀 수 있는 문제입니다. 하지만 List를 사용하면 시간복잡도가 증가해 비효율적인 알고리즘입니다. 따라서 제목에 나타낸 것처럼 heap이라는 자료구조를 사용해야 되는데요. 이러한 문제는 응시자가 효율성에 대한 개념이 있는 지 확인하는 문제입니다. 따라서 효율성을 검증하는 문제를 통해 여러분이 기존 방법대로 풀지 않는, 창의적인 지원자라는 것을 어필합시다!

그러면 시작하겠습니다.

1. 문제소개

---

2. 슈도코드

제가 처음 시도한 방식: 모든 캐릭터의 체력을 리스트에 담고, 배정가능한 아이템을 모두 찾은 후, 모든 배정 가능한 경우의 수를 리스트에 담은 뒤, 가장 높은 공격력을 뽑는다.

즉, 

1) 모든 캐릭터에 대하여
2) 모든 아이템을 순회하며
3) 제일 좋은 아이템을 적용한다.

--->모든 캐릭터의 체력을 하나하나 검색하기 때문에 시간복잡도가 증가함.

여기서 키포인트는 '나보다 체력이 낮은 캐릭터가 쓸 수 있는 아이템은 나도 쓸 수 있다!'라는 것입니다.

이 키포인트를 활용해 조금 더 스마트한 방법을 찾아 봅시다.
1) 모든 캐릭터에 대해
2) 나보다 체력이 낮은 캐릭터가 쓸 수 있는 아이템 + 나부터 쓸 수 있는 아이템을 순회하며
3) 제일 좋은 아이템을 적용한다. -

--->이것이 조금 더 탐색 과정을 줄여주는 방법입니다.

 

따라서 슈도코드는 

1. 쓸 수 있는 아이템 목록을 나타낼 리스트 초기화
2. 내가 쓸 수 있는 아이템을 리스트에 넣기
3. 리스트에서 제일 좋은 아이템을 빼서, 나에게 적용
4. 다음 캐릭터에게 남은 리스트를 넘겨주기
5. 2~4 반복

---

3. 문제풀이

코드 설명은 주석처리 하였습니다.

---

4. 알아야할 스킬셋

item변수를 캐스팅하는 과정에서 enumerate라는 함수를 사용했습니다.

items = [(buff, idx, debuff) for idx, (buff, debuff) in enumerate(items, 1)]

enumerate 는 ‘열거하다’라는 단어입니다. 파이썬에서는 List , Tuple , String 등 여러가지 자료형을 입력받으면 인덱스 값을 포함하는 enumerate 객체를 돌려줍니다. 보통 enumerate 함수는 for문과 함께 자주 사용합니다.

보통

for 인덱스, 값 enumerate(배열, 시작 인덱스)

로 코딩합니다.

 

다양한 예시로 enumerate()에 익숙해져보겠습니다.

예제1)
itemx = ["First", "Second", "Third"] 
for i, val in enumerate(itemx, 10): 
    print("{} 번째 값은 {}입니다".format(i, val))
>>> 10 번쨰 값은 First입니다
>>> 11 번쨰 값은 Second입니다
>>> 12 번쨰 값은 Third입니다

예제2
a = ['hong','gil','dong']
b= []
for i,name in enumerate(a):
    b.append((i,name))
print(b)
>>> [(0, 'hong'), (1, 'gil'), (2, 'dong')]

예제3)
items = [[30,100],[500,30],[100,400]]
items0 = [(*item, idx) for idx, item in enumerate(items,1)]
items0
>>> [(30, 100, 1), (500, 30, 2), (100, 400, 3)]
# *는 unpack 작업을 수행한다.
items1 = [(item, idx) for idx, item in enumerate(items,1)]
items1
>>> [([30, 100], 1), ([500, 30], 2), ([100, 400], 3)]

---

오늘은 프로그래머승의 게임아이템 문제를 힙 자료구조를 활용해 풀어보았습니다.

진또배기 올림