[python][프로그래머스]더 맵게_힙(heap)

 

 

 

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

 

 

 

---

 

생각해야하는 것 : 

heapify를 통해 최소힙으로 만들어 준 후 해야한다. 

 

 

정답 코드[블로그 참조]  : 

import heapq 
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # scoville을 최소 힙화 한다 # 처음 주어질 때는 heap 순서가 아니므로 
    
    while scoville[0] < K : # k를 안넘는동안
        if len(scoville) > 1 : # 1개 이상 남았다면 
            mix = heapq.heappop(scoville) + (heapq.heappop(scoville)*2)
            heapq.heappush(scoville,mix)
            answer+=1 
        else : # 1개 남았다면 # 스코빌이 k를 넘도록 만들수가 없음 
            return -1  
    # k보다 크거나 같을경우 while문을 빠져나옴 
    return answer

 

 

 

정답 코드 2 [복습하면서 내가 짠 코드] : 

 

import heapq 
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville)>1 :
        Min = heapq.heappop(scoville)
        Min2 = heapq.heappop(scoville)
        heapq.heappush(scoville,Min + Min2*2)
        answer+=1 
        if scoville[0] >= K :
            return answer
    if scoville[0] < K : return -1

 

 

 

정답 코드 3 [복습하면서 내가 짠 코드] : 

 

import heapq 
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville : 
        if scoville[0] >= K :
            return answer 
        if len(scoville) ==1 :
            return -1 
        answer +=1 
        Min1 = heapq.heappop(scoville)
        Min2 = heapq.heappop(scoville)
        heapq.heappush(scoville, Min1 + (Min2*2))

 

 

정답 코드 4[복습하면서 내가 짠 코드] : 

 

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K :
        answer +=1 
        Min = heapq.heappop(scoville)
        Min2 = heapq.heappop(scoville)
        heapq.heappush(scoville,Min + Min2*2)
        if len(scoville) == 1 and scoville[0] < K :
            return -1
        
    return answer

---

 

 

 

 

 

 

 

배운점

 

1. python에서의 heap 사용법 

<import heapq> 

 

 

 

2.  못만들 때의 코드를 잘 만들기  (예외처리)

scoville의 크기가 1보다 크면 수행하고 만약 1인데 K보다 작다면 그것은 만들수가 없는 경우다. 

return -1을 해야한다. 

 

 

복습을 할 때마다 코드가 달라진다...신기 

 

 

 

 

 

참고 블로그 : 

https://muhly.tistory.com/78

[Python/알고리즘] 힙 : 더 맵게 (프로그래머스)

 

 

복습 :

 

✅ 20220618

✅ 20220620

✅ 20220622

✅ 20220626

✅ 20220630