[연습] 코딩테스트 - 더 맵게

코딩테스트연습

• programmers.co.kr
• 더 맵게

---

처음에 단순히 list의 pop, append를 이용해서 풀었는데, 정확성은 100%지만 효율성(시간초과) 0%로 나옴.
해결법을 찾다가 나온게 heapq.

import heapq

def solution(scoville, K):
    if len(scoville) == 1:
        if scoville[0] < K:
            return -1
        else:
            return 0

    heapq.heapify(scoville)
    cnt = 0

    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        x = heapq.heappop(scoville)
        y = heapq.heappop(scoville)
        mix = x+y*2
        heapq.heappush(scoville, mix)
        cnt += 1

    return cnt

print(solution([1,2,3,9,10,12], 7))