[Programmers] Lv2. 더 맵게

문제

바로가기

코딩테스트 연습 - 더 맵게

 

풀이

• heapq를 사용하여 풀었다.
• 기존의 scoville배열을 heapify를 사용해 heap구조로 바꿔주고, scoville의 원소가 다 사라질 때까지 반복
• 만약 scoville의 원소가 다 사라져야 반복문이 종료된다면 모든 음식의 스코빌 지수가 K 이상이 될 수 없으므로 -1
• 그렇지 않다면, scoville의 첫 번째 원소가 K 이상이라면 답을 리턴한다.
• 이 과정에서 일단 첫 원소를 빼내고, 만약 두 번째 원소가 존재한다면 두 번째 원소도 빼낸 후 새로운 스코빌 지수를 만들어 push 한다.

 

코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville:
        if scoville[0] >= K:
            return answer
        food1 = heapq.heappop(scoville)
        if scoville:
            food2 = heapq.heappop(scoville)
            heapq.heappush(scoville, food1 + food2 * 2)
        answer += 1
    return -1