[Level 2] 더 맵게

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

문제요약

모든 음식을 스코빌지수 K이상으로 만들기 위해서 스코빌지수가 제일 낮은 음식과 두 번째로 낮은 음식을 일정한 규칙응로 섞는다. 모든 음식의 스코빌지수가 K이상이기 위해서는 몇 번을 섞어야 하는지 구하라

단 모든 음식을 K이상으로 만들지 못할 때는 -1을 출력한다.

---

접근

힙으로 분류가 되었기 때문에 Python의 heapq 모듈을 사용해보았다.

힙에 넣게 되면 계속해서 오름차순으로 정렬되기 때문에 첫 번째와 두 번째 데이터를 꺼내서 계속 섞어주며

예외처리를 해줘야 하낟.

 

구현

heap을 사용할 때는 데이터를 넣을 때 heapq.heappush(list, data)를 사용한다. 괄호 안에 힙을 나타내는 리스트를 넣고 두 번째 인자에 힙에 넣을 데이터를 전달한다.

그렇게 되면 heap 리스트의 데이터들이 오름차순으로 정렬된다.

 

또한 예외처리를 신경써줘야한다.

-1을 return하는 상황은 더 이상 섞어도 K이상으로 만들 수 없을 때이다

그러한 상황은 원소가 하나 남았을 때 K미만일 때, 제일 작은 원소를 꺼냈는데 더 이상 힙에 원소가 없을 때이다.

따라서 이러한 경우에는 바로 -1을 return하도록 하였다.

import heapq
def solution(scoville, K):
    answer = 0
    heap = []
    for idx in range(len(scoville)):
        heapq.heappush(heap, scoville[idx])
    
    while True:
        # 첫 번째 원소가 K이상이면 뒤의 원소도 K이상이기 때문에 바로 종료
        if heap[0] >= K:
            break
        # 현재 힙에 원소가 1개 있는데 그것이 K보다 작다면 -1 return
        if len(heap) == 1 and heap[0] < K:
            return -1
        # 제일 작은 원소를 꺼낸다.
        a = heapq.heappop(heap)
        # 힙에 원소가 남아있다면 두 번째 음식을 꺼내서 섞어줌
        if heap:
            b = heapq.heappop(heap)
            c = a + (b*2)
            heapq.heappush(heap, c)
        # 힙에 원소가 남아있지 않다면 -1을 return    
        else:
            return -1
        answer += 1
    return answer