[알고리즘 연습] 더 맵게 (프로그래머스 lv2, 파이썬)

문제

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

코딩테스트 연습 - 더 맵게

풀이

import heapq

def solution(scoville, k):
    heapq.heapify(scoville)
    i = 0
    while scoville[0] < k:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(
                scoville) + (heapq.heappop(scoville) * 2))
            i += 1
        else:
            return -1
    return i

• 단순 queue 혹은 stack으로는 새로 생성되는 값(섞은 음식의 스코빌 지수)를 정렬하기 어렵다
• heapq 활용 : 우선순위대로 자동정렬해주는 자료구조 (우선순위 큐)
• heapq.heapify(list) : 자료구조 heap화
• heapq.heappush(heap, item) : 힙 구조를 유지하면서 값 삽입
• heapq.heappop(heap) : 가장 작은값 반환
• scoville[0]은 scoville에서 가장 작은 값이다. 해당 값이 k보다 작은 이상 계속해서 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)를 반복한다.
• 만약 scoville의 크기가 1인데 그것이 k보다 작은 스코빌 지수를 가진다면 불가능한 것이므로 -1를 반환한다.