더 맵게 level2

문제를 읽은 후 생각

- queue나 heap을 써야겠다.

- 어떤 음식들을 섞어야 가장 적은 횟수로 정답을 도출할 수 있을까?

ex) K가 3, 음식 배열이 [1, 2, 5, 6] 이면 1과 2 음식을 섞어 1번이 최소가 된다.

ex) K가 7, 음식 배열이 [1, 2, 9, 10]이면 1과 2를 섞은 후 그 결과인 5와 9를 섞는다. 총 2번임

다른 방법으로는 1과 10을 섞고 2와 9를 섞으면 된다. 이것도 총 2번임

 

2가지 방법을 정리하면 첫 번째 방법은 가장 안 매운 음식 2가지를 섞는 방식이고 두 번째 방법은 가장 안 매운 음식과 가장 매운 음식을 섞는 방법인데 두 번째 방법으로 하면 첫 번째 예시 또한 2번이란 결과가 나오게 된다. 그러므로 첫 번째 방법으로 문제를 풀기로 하였다.

 

가장 안 매운 음식을 자동?으로 가져오기 위해 heap을 사용하였다.

 

코드

import heapq

def solution(scoville, K):
    cnt = 0
    heap = []
    
    for i in scoville:
        heapq.heappush(heap, i)
    
    while heap[0] <= K and len(heap) != 1:
        a, b = heapq.heappop(heap), heapq.heappop(heap)
        tmp = a + (b * 2)
        cnt += 1
        heapq.heappush(heap, tmp)
    
    if heap[0] < K:
        return -1
    return cnt

 

고찰

- 난 항상 while이나 for loop을 쓴 후 마지막에 조건문을 하나 더 사용하는 것 같다. 이게 더 쉽다고 생각하는 듯...

- while문 안에서 처리하는 방법을 생각해보면 현재 나의 코드의 while문 조건을 while문 안에서 확인하고 while True로 하면 될 것 같다.

 

ex)

    while True:
        a = heap.heappop(heap)
        if a >= K:
        	break
        if len(heap) == 0:
        	return -1
        cnt += 1
        b = heap.heappop(heap)
        tmp = a + (b * 2)
        heapq.heappush(heap, tmp)