[프로그래머스/python] 더 맵게

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

프로그래머스

 

풀이방법:

• 최소 값을 연산하는 문제이므로, heapq를 사용했습니다.
• 종료 조건으로는 K 값을 구할 수 없는 경우(즉, 배열의 요소가 1개만 남아있고 그 값이 K보다 작은 경우) 와 최소 값이 K보다 크거나 한 개의 요소만 남아 더 이상 연산할 수 없는 경우로 설정하였습니다.
• scoville 배열이 정렬되어있다는 보장이 없는데, heapify() 함수를 통해 정렬해주지 않아 시간을 많이 잡아먹었습니다.

풀이코드:

import heapq
def solution(scoville, K):
    answer = 0

    heapq.heapify(scoville)
    while True:
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        if scoville[0] >= K or len(scoville) == 1:
            break
        val1 = heapq.heappop(scoville)
        val2 = heapq.heappop(scoville)
        heapq.heappush(scoville, val1 + val2*2)
        answer+=1


    return answer