[프로그래머스][heap] 게임아이템 python (201005)

1. 문제 설명

 

 

 

 

2. 풀이 

 

 

1) 공격력이 쎈 순으로 정렬 - 실패 

 

import heapq

def solution(healths, items):

    # 플레이어 체력 오름차순으로 정
    healths.sort()

    # 아이템 리스트 딕셔너리로 만들어두기
    item_id_dict = {one_item[0] : idx+1 for idx, one_item in enumerate(items)}
    # print(item_id_dict)

    items.sort(key = lambda x : x[0]) # 공격력이 쎈 순으로 정렬
    # print(items)

    result_list = []
    str_player = healths.pop() # 가장 공격력이 쎈 플레이어
    for now_item in items:
        # print(now_item)
        if healths:
            if str_player - now_item[1] >= 100: # 선수가 공격을 써 100이 남는경우
                heapq.heappush(result_list, item_id_dict[now_item[0]]) # 해당 공격 실행
                str_player = healths.pop() # 그 다음 공격 쎈 사람으로 변경
            else:
                pass
        else:
            break
    return result_list.sort()

healths = [200,120,150]
items = [[30,100],[500,30],[100,400]]
solution(healths, items)

-> 공격력이 쎈 순이 아니라 약한 순서대로 탐색을 해야한다. 디큐를 함께 써야한다. 

 

 

2) 순서 약한 순서대로, 마지막 결과 heap 으로 받기 -> 실패 

import heapq
from collections import deque

def solution(healths, items):

    # 플레이어 체력 오름차순으로 정
    healths.sort()
    items = [(*item, idx) for idx, item in enumerate(items, 1)]
    items.sort(key = lambda x : x[1]) # 1) 피해 기준 오름차
    items = deque(items)
    # print(items)

    candidate = []
    result_list = []

    for player in healths:
        # print(items[1])
        while items and player - items[0][1] >=100 :
            item = items.popleft() # 지금 쓸수 잇는 아이
            heapq.heappush(candidate, (-item[0],item[2])) # 아이템 공격력 큰게 가장 앞에 가도록
        if candidate :
            big_idx = heapq.heappop(candidate)[1] # 담긴 애들중 가장 큰놈을 꺼내
            heapq.heappush(result_list, big_idx) # 해당 인덱스 넣어주기

    return result_list

 

 

3) 순서 약한 순서대로, 마지막 결과 리스트로 받고 재정렬  -> 통과

 

import heapq
from collections import deque

def solution(healths, items):

    # 플레이어 체력 오름차순으로 정
    healths.sort()
    items = [(*item, idx) for idx, item in enumerate(items, 1)]
    items.sort(key = lambda x : x[1]) # 1) 피해 기준 오름차
    items = deque(items)
    # print(items)

    candidate = []
    result_list = []

    for player in healths:
        # print(items[1])
        while items and player - items[0][1] >=100 :
            item = items.popleft() # 지금 쓸수 잇는 아이
            heapq.heappush(candidate, (-item[0],item[2])) # 아이템 공격력 큰게 가장 앞에 가도록
        if candidate :
            big_idx = heapq.heappop(candidate)[1] # 담긴 애들중 가장 큰놈을 꺼내
            result_list.append(big_idx) # 해당 인덱스 넣어주기
            
    result_list.sort()
    return result_list

 

 

3. 정리 

2번, 3번의 차이는 마지막 인덱스를 담는 형식의 차이인데 왜 2번에서 에러가 떴는지 모르겠다. 

나는 오히려 3번이 시간복잡도에서 더 문제가 될꺼라 생각했는데... (sort를 세번이나 썼는데도 런타임에러 아니라니 알다가도 모를...)

 

더 찾아봐야할점 - heappush 로 넣었을때와, 그냥 리스트 sort 때렸을때 결과가 다른가?