프로그래머스 더 맵게 파이썬

프로그래머스 파이썬 더 맵게 프로그래머스 더 맵게 파이썬 파이썬 프로그래머스 더 맵게 파이썬 더 맵게 프로그래머스 더 맵게 프로그래머스 파이썬 더 맵게 파이썬 프로그래머스

더 맵게

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

문제 단순화

• scoville 정수 배열이 있다.
• scoville 배열의 첫 번째 최소값을 m1, 두 번째 최소값을 m2라 가정한다.
• m1과 m2를 제거하고, m1+(m2*2) 값을 scoville 배열에 추가한다.
• scoville 배열의 모든 값이 정수 K 이상 될 때까지 반복하고, 반복한 횟수를 리턴한다.
• K 이상 만들 수 없는 경우 -1을 리턴한다.

문제풀이

• heapq를 이용하여 scoville을 최소힙으로 만든다.
• 두 최소값을 제거하고 계산한 결과가 하나씩 추가되므로, 최대 연산 횟수는 len(scoville)-1 이다.
• len(scoville)-1 만큼 최소값 갱신 연산을 수행하고, 최소 힙의 첫 번째 값(최소값)이 K 이상 일 때, answer에 연산횟수를 갱신한다.
• answer에 연산횟수가 갱신되지 않을 경우 -1, 갱신되면 연산횟수를 리턴한다.

코드

import heapq as hq

def solution(scoville, K):
    answer = -1
    hq.heapify(scoville)
    for i in range(1,len(scoville)):
        hq.heappush(scoville, hq.heappop(scoville) + hq.heappop(scoville)*2)
        if scoville[0] >= K:
            answer = i
            break
    return answer