[Programmers]Lv 2.더 맵게

문제:

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 *2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

단순하게 scoville 배열을 정렬한 뒤에 첫 번째 인덱스값이 K보다 커지는 순간까지 섞는 과정을 반복하면 된다고 생각했다.

따라서 다음과 같이 코드를 작성할 수 있었다. 중간에 elif 조건으로 scoville 배열이 1인지 확인을 하였는데 이 경우에 더 이상 섞지 못하는 경우이기 때문에 -1을 반환하는 경우인 것이다.

def solution(scoville,K):
    count=0
    while(True):
        scoville.sort()
        if scoville[0]>K:
            break
        elif len(scoville)==1:
            return -1
        else:
            count+=1
            a=scoville.pop(0)
            b=scoville.pop(0)
            scoville.append(a+2*b)
    return count

 하지만 이 방법은 효율성 테스트에서 시간초과로 통과하지 못한다. 이 문제의 태그가 힙(heap)이므로 힙을 사용하도록 코드를 수정하였다.

힙이란 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로 완전이진트리로 구성되어 있다. 힙에는 최대 힙과 최소 힙 두 가지가 있다. 힙은 부모노드와 자식 노드와만 대소 관계가 존재하는데 부모 노드가 큰 경우가 최대 힙, 자식 노드가 큰 경우가 최소 힙이다.

 파이썬에서는 힙 구조를 구현할 수 있도록 모듈을 제공한다. import heapq 로 불러와서 사용을 한다. heapq는 부모 노드가 자식 노드보다 항상 작거나 같은 최소 힙을 제공한다. 따라서 가장 작은 요소가 0 인덱스를 가지며 pop을 했을 경우에 가장 작은 값이 나온다.

이번 문제를 해결하기 위해 heapq.heappush(heap,item)과 heapq.heappop(heap)을 사용했다.

heapq.heappush(heap,item)은 힙의 구조를 유지하면서 heap에 item을 넣는 것이고 heapq.heappop(heap)은 가장 작은 값을 반환하며 이 역시 힙의 구조를 유지한다. 따라서 위의 코드를 heap 구조를 유지하면서 해결하도록 수정하였다.

import heapq
def solution(scoville,K):
    count=0
    h=[]
    for i in scoville:
        heapq.heappush(h,i)
    while(True):
        if h[0]>=K:
            return count
        elif len(h)==1:
            return -1
        else:
            a=heapq.heappop(h)
            b=heapq.heappop(h)
            heapq.heappush(h,a+b*2)
            count+=1