[Python] 더 맵게

1. 문제

 

 

 

2. 풀이과정

 

방법 1) heapq 내장 모듈 활용

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)

    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        answer += 1
        #가장 안매운거, 두 번째 안매운거 heap에서 빼서 연산
        a = heapq.heappop(scoville) + heapq.heappop(scoville)*2
        #섞은거 넣기
        heapq.heappush(scoville, a)

    return answer

 

방법 2) heapq대신 deque만 이용하였다. 섞은 결과는 새로운 배열 mix에 따로 저장하여 scoville와 mix의 맨 앞 원소만 비교하였다. 결과적으로 방법 1)보다 약 1.5배 더 빠른 속도가 나왔다.

from collections import deque

def solution(scoville, K):
    answer = 0 
    mix = deque()
    scoville.sort()
    sco = deque(i for i in scoville)
    
    while (sco and sco[0] < K) or (mix and mix[0] < K):
        answer += 1
        if len(sco) + len(mix) <= 1:
            return -1
        
        food = [0]*2
        for a in range(2):
            if sco and mix:
                if sco[0] < mix[0]:
                    food[a] = sco.popleft()
                else:
                    food[a] = mix.popleft()
            elif sco:
                food[a] = sco.popleft()
            else:
                food[a] = mix.popleft()
            
        mix.append(food[0]+food[1]*2)
        
    return answer