[프로그래머스] 더 맵게

더 맵게 | Lv.2
https://school.programmers.co.kr/learn/courses/30/lessons/42626

 

 

 

작성 코드

 

queue 이용한 풀이

 

from collections import deque

def solution(scoville, K):
    answer = 0
    queue = deque(sorted(scoville))
    while queue:
        if queue[0] >= K:
            return answer
        elif len(queue) < 2:
            return -1
        else:
            a = queue.popleft()
            b = queue.popleft()
            queue.appendleft(a + 2 * b)
        print(queue)

 

• 문제 분류는 heap이었지만 queue로도 풀 수 있지 않을까 생각함
• [1, 2, 3, 9, 10, 12] -> [5, 3, 9, 10, 12] -> [11, 9, 10, 12] : 가장 작은 두 가지의 값을 연산한 것이 다음 연산에서 [0] 임을 보장할 수 없음 -> 그래서 heap을 쓰는 것

 

 

heap 이용한 풀이

 

import heapq
from heapq import heapify

def solution(scoville, K):
        answer = 0
        heapify(scoville)
        while scoville:
            if scoville[0] >= K:
                return answer
            elif len(scoville) <= 1:
                return -1
            else:
                # heapq.heappush(scoville, heappop(scoville) + (heappop(scoville)*2))
                a = heapq.heappop(scoville)
                b = heapq.heappop(scoville)
                heapq.heappush(scoville, a + b*2)
                answer += 1

 

• heapify : list to heap
• while 문 내 if, elif 의 순서를 바꾼다면 몇 가지 test case에서 오답(len이 1인 답이 있을 수 있음, 순서 중요!!)
• 주석처리한 코드는 밑의 세 줄과 동일한 역할