[알고리즘 풀이] 프로그래머스 : 더 맵게, Level2(Heap)

아래는 문제링크

https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3#

알고리즘 연습 - 더 맵게 | 프로그래머스

정확성에서는 통과했으나

효율성에서 실패.

 

 

실패 1 (sort가 많아서 실패)

1번 sort()가 많아서 실패
def solution(scoville, K):
    answer = 0
    
    while len(scoville) >=1 : 
        if min(scoville) >= K :
            return answer
        else :
            if len(scoville) == 1 :
                return -1
            scoville.sort()
            new_value = scoville[0] + scoville[1] * 2
            scoville = scoville[2:]
            scoville.insert(0,new_value)
            answer = answer + 1
            
    return answer

 

 

실패 2 (sort 사용안하고 그때 그때 정렬하려고해도 실패)

def solution(sco, K):
    answer = 0
    sco.sort()
    
    while len(sco) >=1 : 
        if sco[0] >= K :
            return answer
        else :
            if len(sco) == 1 :
                return -1
            v1, v2 = sco[0], sco[1]      
            new_value = v1 + v2 * 2
            sco = sco[2:]
            i_index = 0
            if len(sco) == 0 :
                sco.insert(0,new_value)
            else : 
                if new_value >= max(sco) :
                    sco.insert(len(sco),new_value)
                else : 
                    for i,j in enumerate(sco) :
                        if j >= new_value :
                            i_index = i
                            break                    
                    sco.insert(i_index,new_value)
 
            answer = answer + 1
    return answer

 

구글에서 검색한 heapq로 성공

import heapq
 
def solution(sco, K):
    answer = 0
    s_heap = []
    
    for i in sco :
        heapq.heappush(s_heap, i)
 
    while s_heap[0] <= K :
        if len(s_heap) == 1 :
            return -1
        else :
            heapq.heappush(s_heap, heapq.heappop(s_heap) + heapq.heappop(s_heap) *2)
            answer = answer + 1
 
    return answer

 

heapq에 대해서 참고한 사이트 링크

 

http://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법