[프로그래머스] 더 맵게 - (python 파이썬)

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

문제풀이 : 처음에 힙을 안쓰고 배열에서 무작정 sort 한뒤 꺼내고 다시 넣고 과정을

반복하다가 역시 시간초과가 떴다. 힙을 사용해줘야 O(logn)의 시간복잡도를 가지고,

런타임 없이 해결된다. 또 다른사람의 풀이를 참고하면서 try, except로 훨씬 깔끔하게,

코딩할 수 있었다. 매개변수로 받은 배열 heapify를 통하여 scoville(=heap)을

정리해주고, heappop을 통해 가장 작은 원소인 루트를 뽑아주면서, heappush를 통해

원소를 대입해준다. 각각 pop과 push는 O(log(n))의 시간복잡도를 가진다.

import heapq

def solution(scoville, K):
    count_mix = 0
    heap = scoville
    heapq.heapify(heap)

    while heap[0] < K:
        try:
            new_food = heapq.heappop(heap) + heapq.heappop(heap)*2
            heapq.heappush(heap,new_food)
            count_mix += 1
        except IndexError:
            return -1

    return count_mix

답(이미지)

후기 : 포인트1) 힙 사용   포인트2) try, except 문 사용