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

문제 접근

• 힙의 특징을 이용하여 문제를 푼다.

문제 해결

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

# 정렬 시간 복잡도 NlogN, 삽입 삭제 logN
# heapq.heappush() 삽입
# heapq.heappop() 꺼냄

import heapq

def solution(scoville, K):
    # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 return
    answer = -1
    count = 0
    flag = True
    h = []
    for value in scoville:
        heapq.heappush(h, value)
    # pop 하면서 스코빌 지수와 체크 하며 섞을지 말지 정하기

    # 힙이니까 계속 자동 정렬 될 것이다.
    while True:
        if h[0] < K:
            # 더 이상 K를 충족할 수 없는 경우
            if len(h) == 1:
                flag = False
                break
            else:
                first = heapq.heappop(h)
                second = heapq.heappop(h)

                new_scoville = first + (second * 2)
                heapq.heappush(h, new_scoville)
                count += 1
        # 가장 작은 값이 스코빌지수가 K이상이라면 종료
        else:
            break
    if flag == True:
        answer = count
    return answer