[프로그래머스][힙] 더 맵게

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

코딩테스트 연습 - 더 맵게

 

자료구조 heapq 를 공부하니 의외로 쉽게 문제가 풀렸다.

2021.08.11 - [Study/자료구조 & 알고리즘] - [자료구조] heap(힙 자료구조) / Python heapq(힙큐)

[자료구조] heap(힙 자료구조) / Python heapq(힙큐)

 

idea

1. scoville을 최소힙으로 정렬한다. 첫번째 원소(루트노드) 가 K보다 작으면 항상 주어진 연산을 수행한다.
2. 두 음식을 섞어 새로운 음식을 만들기 때문에 연산을 할수록 scoville의 원소의 갯수가 줄어든다.
   따라서 수행 도중 스코빌의 길이가 2가 되지 않는다면 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우이다.
3. 섞은 음식의 스코빌 지수를 push 할 때마다 섞은 횟수를 1 씩 증가시킨다.

import heapq as hq

def solution(scoville, K):
    hq.heapify(scoville)
    answer = 0
    
    while scoville[0] < K:
        if (len(scoville) < 2):
            return -1
        first = hq.heappop(scoville)
        second = hq.heappop(scoville)
        tmp = first + (second * 2)
        hq.heappush(scoville, tmp)
        answer += 1 
    
    return answer