728x90
반응형
문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/42626
풀이:
import heapq
def solution(scoville, K):
count = 0
heapq.heapify(scoville)
while scoville[0] < K :
heapq.heappush(scoville, heapq.heappop(scoville) + (heapq.heappop(scoville)*2))
count += 1
if len(scoville) == 1 and scoville[0] < K :
return -1
return count
heap 의 구조
def solution(x):
nums = [1,5,4,8,7,3]
heap = []
for i in nums:
heapq.heappush(heap , (-i,i)) # 최댓값 구할때 튜플형식으로 해줌
# 튜플형식이 아닌 i 이면 최솟값 순으로 나옴
while heap:
print(heapq.heappop(heap))
# 1 ---> root 이런느낌
# / \
# 3 5
# / \ /
# 4 8 7
효율 실패 코드:
heapify 대신에 정렬을
이분탐색으로 인덱스를 찾아서 넣는 방식으로해봤다.
def solution(scovilles, K):
scovilles.sort()
scoville = deque(scovilles)
count = 0
while scoville[0] < K:
left, right = scoville[0], scoville[1]
# del scoville[0]
# del scoville[0]
scoville.popleft()
scoville.popleft()
new_node = left + (right * 2)
insert_value(scoville, new_node)
count += 1
if len(scoville) == 1 and scoville[0] < K:
return -1
return count
def insert_value(lst, value):
# 이분 탐색을
left, right = 0, len(lst)
while left < right:
mid = (left + right) // 2
if lst[mid] < value:
left = mid + 1
else:
right = mid
lst.insert(left, value)
print(solution([1, 3, 2, 9, 10, 12], 7))
이거 역시 효율성에서 0 점이 나온다.
반응형
댓글