heap4 [자료구조] 게임 아이템 파이썬 (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 healt.. 2021. 4. 25. [자료구조] 배달 파이썬 (BFS, queue, Dijkstra, heap) from math import inf from collections import defaultdict, deque from itertools import product def solution(N, roads, K): answer = [inf, 0] + [inf for i in range(N-1)] # print(answer) # why 처음이 0이 아니라 inf로 설정했을까? -> zero 인덱스 문제를 편하게 하려고 map = defaultdict(list) # 리스트 형태로 받겠다. dist_map = [[inf for _ in range(N+1)] for _ in range(N+1)] # print(dist_map) # for road in roads: a,b,dist = road map[a].ap.. 2021. 4. 23. [자료구조] 배상 비용 최소화 파이썬 (heap) def solution(no, works): # max_idx = works.index(max(works)) # works[works.index(max(works))] -= 1 while no > 0: # reach 0 exit max_idx = works.index(max(works)) works[max_idx] -= 1 no -= 1 return sum([x**2 if x > 0 else 0 for x in works]) return할때 0보다 큰 조건을 안넣어줘서 오답이 나온것 같아서 넣어줬더니 통과했다. 일단 여기까지는 했는데 효율성에서 통과를 못했다 시간을 줄일 수 있는 부분이 while문 안에서 해결되어야 될거 같은데 음. sorted로 사용하니까 통과하긴 하는데 오래걸리긴 한다. def so.. 2021. 4. 22. [Python] Heap import heapq def my_heap_example(L, T): """ 주어진 비커의 리스트를 힙 구조로 변환 """ heapq.heapify(L) result = 0 while len(L) >= 2 : #IndexError 방지 """ 힙에서 최솟값을 가져옴 """ min_ = heapq.heappop(L) if min_ >= T: # 액체의 최솟값이 T보다 크다는 조건 만족(종료) print("-"*40, "\nresult:", result) return result else: # 두 번째로 작은 값 가져와서 합친 값을 힙에 삽입 min_2 = heapq.heappop(L) heapq.heappush(L, min_ + min_2*2) result += 1 print("step{}: [{},{}.. 2021. 3. 10. 이전 1 다음