코테연습 - 힙(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 합니다.
입출력 예
scoville K return
[1, 2, 3, 9, 10, 12] 7 2
입출력 예 설명
스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

먼저 scoville 배열에 있는 수들을 오름차순으로 정렬하고
K이상이 될 때까지 작은 순서대로 섞고 answer에 1씩 저장한다.

(초기에 고뇌의 흔적..)

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)

    while scoville[0]<K:
        answer += 1
        if len(scoville)>1:
            heapq.heappush(scoville,heapq.heappop(scoville)+(heapq.heappop(scoville)*2))

        else :
            return -1

    return answer

+)Heap 이란
Heap 이란 자료구조 형태 중 하나로서 우선순위 큐를 위해 만들어진 구조이다.

(자세한 Heap에 대해 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 참고)

코딩 테스트 문제 중 최솟값 , 혹은 최댓값을 계속해서 호출해야 하는 상황인 경우 Heap 구조를 이용하여 구현하면 시간측면에서 굉장히 효율적인 구현이 가능하다.

import heapq
heapq 모듈을 이용하여 힙 자료구조를 사용할 수 있다. heapq 는 내장 모듈이므로 따로 설치가 필요하지 않는다.

기본적으로 Min-priority-queue 구조를 가지고 있다.

import heapq

기존 배열을 Heap 구조로 - heapify()

testheap = [1,3,2,6,8,0,6]
heapq.heapify(testheap)
print(testheap)

print 결과값 => Heap 구조로 변했다.
[0, 3, 1, 6, 8, 2, 6]
Heap 에 요소 추가하기 - heappush(배열이름, 요소)

testheap = []
heapq.heappush(testheap, 3)
heapq.heappush(testheap, 5)
heapq.heappush(testheap, 1)
heapq.heappush(testheap, -3)
print(testheap)

#print 결과값 =>
[-3, 1, 3, 5]

Heap 요소를 삭제하기 - heappop(배열이름)

testheap = []
heapq.heappush(testheap, 3)
heapq.heappush(testheap, 5)
heapq.heappush(testheap, 1)
heapq.heappush(testheap, -3)
heapq.heappop(testheap)
heapq.heappop(testheap)
print(testheap)

print 결과값 =>
[3, 5]
힙 요소를 1개씩 삭제할 수 있다.

요소 2개가 삭제되었다. 삭제를 해도 자동으로 힙 구조는 유지된다!

출처: https://programming119.tistory.com/85 [개발자 아저씨들 힘을모아]