더 맵게

링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

(프로그래머스>코딩테스트 연습>힙(Heap)>더 맵게)

 

---

 

<문제>

 

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

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

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

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

---

 

 

<내가 작성한 코드>

 

import heapq
def solution(scoville,K):
    answer =0
    scoville_heap = []
    for item in scoville:
        heapq.heappush(scoville_heap,item)
    while(True):
        temp = heapq.heappop(scoville_heap)
        if(temp>=K):
            break
        else:
            answer+=1
            if(len(scoville_heap)>0):
                temp2=heapq.heappop(scoville_heap)
                heapq.heappush(scoville_heap,temp+temp2*2)
            else:
                return -1
    return answer

 

 

---

 

<참고한 개념>

 

• heap :  모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리(가장 작은 요소가 항상 루트인 heap[0]이다)
• heapq.heappush(heap, item) : 힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.
• heapq.heappop(heap) : 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환. 힙이 비어 있으면, IndexError가 발생
• heapq.heappushpop(heap, item) : 힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환
• heapq.heapify(x) : 리스트 x를 선형 시간으로 제자리에서 힙으로 변환
• heapq.heapreplace(heap, item) : heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시, 힙 크기는 변경X, 힙이 비어 있으면, IndexError가 발생
• heapq.merge(*iterables, key=None, reverse=False) : 여러 정렬된 입력을 단일 정렬된 출력으로 병합
• heapq.nlargest(n, iterable, key=None) : iterable에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환
• heapq.nsmallest(n, iterable, key=None) : iterable에 의해 정의된 데이터 집합에서 n 개의 가장 작은 요소로 구성된 리스트를 반환