문제 설명

매운 것을 좋아하는 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 합니다.

코드 작성

1차 코드 작성

힙을 사용해야한다는건 알고 있었지만, 혹시 힙을 사용하지 않는 방법도 가능한가 싶어 처음에는 힙 없이 풀어보았다.

def solution(scoville, K):
    return  hotter(scoville, K, 0)

def hotter(scoville, K, answer):
    if scoville[0] >= K :
        return answer

    food = [scoville[0] + (scoville[1] * 2)] + scoville[2:]
    answer += 1
    return hotter(food, K, answer)

문제점

1. 찾지 못하는 경우 고려하지 않음.
2. scoville이 정렬되어 있을거라는 보장X -> 정렬하는 과정이 필요함
3. 정렬하는데 O(nlogn)소요 예정 + 재귀 최악의 경우 O(n) 소요. 효율성에서 떨어짐

=> heap을 써야한다 😂

2차 코드 작성

파이썬에서 힙을 사용하는 방법을 몰라 공부하는 시간을 가졌다.
힙 라이브러리 사용방법만 알고있다면 완전 수월한 문제!

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while(scoville[0] < K and len(scoville) > 1):
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a + (b*2))
        answer += 1
        
    if scoville[0] < K:
        answer = -1

    return answer

what i learned

heap

https://www.geeksforgeeks.org/heap-data-structure/
heap은 완전이진트리로 두가지 타입으로 나뉜다.

min-heap

가장 작은 숫자가 root가 된다. 항상 부모노드는 자식노드보다 작은 수를 갖는다.

max-heap

가장 큰 숫자가 root가 된다. 항상 부모노드는 자식노드보다 큰 수를 갖는다.

heap을 array로 표현시

https://www.geeksforgeeks.org/array-representation-of-binary-heap/

항상 root노드는 0번째 인덱스
i번째 노드에 대하여

• (i-1)/2 -> 부모노드
• (2*i)+1 -> 왼쪽 자식노드
• (2*i)+2 -> 오른쪽 자식노드

JS에서 heap 구현하는 방법
https://blog.bitsrc.io/implementing-heaps-in-javascript-c3fbf1cb2e65

heapq

참고 https://www.daleseo.com/python-heapq/

heapq import 하기

import heapq

heapq 생성

list를 생성하는것과 같다!
hq = []

heapush

힙 트리에 원소를 넣는 방법
heapq.heappush(hq, 3)

넣은 원소가 힙에 있는 요소 중 가장 작은 요소면, root의 값으로 변경해준다. hq[0]으로 접근 가능하다.

hq[0]이 가장 작은 원소라고 해서 hq[1]이 두번째로 작은 원소라는 보장은 없다. heap 배열에서는 가장 작은 요소만 보장할 뿐 나머지 순서는 보장할 수 없다.

heappop

가장 작은 요소인 hp[0]을 삭제 후, 리턴한다.
heapq.heappop()

기존의 hq[0]가 사라지면서 새로운 hq[0]로 힙에 남은 원소 중 가장 작은 요소가 선택된다.

기존 리스트를 heap으로 변환

heapq.heapify(hp)
hp [ ] 원본이 heapq로 변해서, 따로 변수에 넣어줄 필요가 없다.(리턴값 없음)