[Programmers] 힙 : 더 맵게 (Python)

1일 1문제 60일차!

오늘의 문제는 프로그래머스의 더 맵게 입니다.

프로그래머스

첫번째 시도

def solution(scoville, K):
    answer = -1
    
    count = 0
    
    check_flag = False
    
    while min(scoville) < K:
        scoville = sorted(scoville, reverse=True)
        
        scoville.append(scoville.pop() + (scoville.pop() * 2) )

        if len(scoville) == 1 and scoville[0] < K:
            check_flag = True
            break
        
        count = count + 1
    if check_flag == False:
        answer = count
        
    return answer

정확성에서는 제대로 결과가 나왔지만 효율성에서는 시간초과라는 결과가 나왔습니다.

 

매번 정렬하는 부분에서 시간이 초과 된 것으로 보입니다.

 

두번째 시도

heapq라는 것을 활용하여 구현해보았습니다.

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판

import heapq

def solution(scoville, K):
    answer = -1
    
    count = 0
    
    check_flag = False
    
    heapq_scoville = heapq.heapify(scoville)
    
    while scoville[0] < K:
        min_first = heapq.heappop(scoville)
        min_second = heapq.heappop(scoville)
        
        heapq.heappush(scoville, min_first + (min_second * 2))
        

        if len(scoville) == 1 and scoville[0] < K:
            check_flag = True
            break
        
        count = count + 1
    if check_flag == False:
        answer = count
        
    return answer

 

SOMJANG/CODINGTEST_PRACTICE