힙_더 맵게_python

문제 설명

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

---

문제 접근 방법

1. heapify와 힙 정렬을 통해 주어진 배열을 힙으로 만들고 내림차순 정렬을 통해 해결하려고 하였지만 입출력만 통과할뿐 대부분 테스트에서 통과하지 않았다. 가능한 배운내용을 활용하고 풀고 싶었지만, 통과를 할 수 없었다.

2. 파이썬 heapq 라이브러리

소스를 얻기 위해 구글링을 해보니 파이썬의 heapq 라는 라이브러리에 대해 알게 되었다.

파이썬의 heapq 라는 내장모듈을 통해 힙 우선순위 큐 알고리즘을 제공하는 미친 효율의 라이브러리가 있었다.

우리는 구현에 신경쓰지 않고 기능만을 사용하여 이 문제를 풀 수 있었다.

실제로 내부구조를 들여다보니 push, pop, replace등 다양한 함수들을 제공했다.

참고 : github.com/python/cpython/blob/master/Lib/heapq.py

해당 문제는 heapq를 사용하지 않고는 모두 런타임 에러를 발생시킨다고 한다.

먼저 주어진 배열을 힙으로 변환한다. 이때 heap은 min heap이 디폴트이다. 따라서 0번째 인덱스는 항상! 가장 작은 값이 되며 이 특성을 이용해 스코빌 지수 이상이 될 경우 반복문을 종료한다.

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 한다라는 제약이 있다.

스코빌 넘버를 반복할 수록 pop을 2번 push를 1번 사용하였기에 언젠가는 힙의 길이가 0이 된다. 길이가 0이 될때까지 앞의 조건문을 만족하지 못할경우 예외처리 -1을 리턴한다.

import heapq

def solution(scoville, K):
    answer = 0
    # 배열을 힙으로 변환
    heapq.heapify(scoville)

    # 0번째 인덱스가 가장 작은 값(min heap)
    # 기본적으로 heapq는 min heap을 default로 함
    while True:
        number_1 = heapq.heappop(scoville)
        if number_1 >= K:
            break
        if len(scoville) == 0:
            return -1
        number_2 = heapq.heappop(scoville)
        scoville_number = number_1 + (number_2 * 2)
        heapq.heappush(scoville, scoville_number)
        answer += 1
        
    return answer

---

시간복잡도

1. heapq=> heapify

heap을 공부할때 heapify 함수를 만들며 heapify의 시간복자도는 O(logN)라고 알고 있었다.

heapq의 heapify 함수는 단순히 heapify 알고리즘 한번을 실행하는 것이 아닌 힙 정렬로 배열을 힙으로 변환한다.

heapq의 heapify 함수는 O(N)이라는 의견도 있지만, O(NlogN)이 더 정확한 것 같다.

(참고 : yunaaaas.tistory.com/36)

아래는 heapq 라이브러리의 내부구조이다.

def heapify(x):
    """Transform list into a heap, in-place, in O(len(x)) time."""
    n = len(x)
    # Transform bottom-up.  The largest index there's any point to looking at
    # is the largest with a child index in-range, so must have 2*i + 1 < n,
    # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
    # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
    # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
    for i in reversed(range(n//2)):
        _siftup(x, i)
        
def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)
    
def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

heapify의 경우 배열 내부의 원소들이 _siftup, _siftdown 메서드를 이용해 힙 구조에 맞게 노드의 위치를 재배치한다.

_siftup의 경우 왼쪽 자식 노드를 찾고 이 왼쪽 자식노드가 힙의 마지막 노드보다 커질때까지 재배치 되며

_siftdown의 경우 부모노드가 힙 속성을 위배할 경우 부모노드를 트리 아래쪽으로 재배치 시키며 힙 속성을 유지한다.

이때 최소값이 가장 첫번째 인덱스로 위치하게 된다.

힙의 경우 완전 이진트리로 노드의 개수가 N일때 반복문처럼 N번 반복하지 않는다. 이는 힙_1, 힙_2 포스팅했듯이 최악의경우 트리의 높이(logN)만큼 비례하기 때문이다.

아래 설명할 heappop(), heappush()의 삽입과 삭제 연산의 경우 _siftup 함수를 호출하며 이는 O(logN)이다.

즉, heapq 라이브러리에서의 heapify 시간 복잡도의경우 O(NlogN) 을 갖는다 볼 수 있다.

---

2. heapq => heappop()

def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt

O(1), O(1)도 있지만 _siftup 재배치 과정은 트리의 높이인 logN과 비례하며, 시간복잡도는 O(logN)이다.

3. heapq => heappush()

def heappushpop(heap, item):
    """Fast version of a heappush followed by a heappop."""
    if heap and heap[0] < item:
        item, heap[0] = heap[0], item
        _siftup(heap, 0)
    return item

동일.

---

해답의 총 시간복잡도는 O(NlogN)으로 생각된다!

import heapq

def solution(scoville, K):
    answer = 0
    # 배열을 힙으로 변환
    heapq.heapify(scoville)

    # 0번째 인덱스가 가장 작은 값(min heap)
    # 기본적으로 heapq는 min heap을 default로 함
    while True:
        number_1 = heapq.heappop(scoville)
        if number_1 >= K:
            break
        if len(scoville) == 0:
            return -1
        number_2 = heapq.heappop(scoville)
        scoville_number = number_1 + (number_2 * 2)
        heapq.heappush(scoville, scoville_number)
        answer += 1
        
    return answer

 

참고 :

stackoverflow.com/questions/38806202/whats-the-time-complexity-of-functions-in-heapq-library/38833175

github.com/python/cpython/blob/fe240882936d8b16b968b9a7adce6b2b3de4e7eb/Lib/heapq.py#L205

yunaaaas.tistory.com/36