[Python] 더 맵게 - 힙

 

 

 

 

---

문제

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

프로그래머스

 

코드

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville) #힙 자료형으로 만들어줌

    mix_count = 0

    while scoville[0] < K:
        if len(scoville) < 2:
            return -1

        new_scovile = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, new_scovile)

        mix_count +=1

    return mix_count

 

 

 

 

다른 사람 코드

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    size, cnt = len(scoville) - 1, 0
    f = heapq.heappop(scoville)
    while size > 0:
        s = heapq.heappop(scoville)
        f = heapq.heappushpop(scoville, f + s + s)
        if f >= K:
            return cnt + 1
        cnt += 1
        size -= 1
    return -1

 

 

 

접근법

https://geunuk.tistory.com/86#%ED%-E%--%---Heap-%--%EC%-D%--%--%EB%B-%B-%EC%--%B-%EB%A-%-C%--%EA%B-%AC%ED%--%--

힙 자료 구조를 사용해야 한다 위 블로그가 힙 자료구조에 대해 아주 잘 설명해둔 블로그이다

 

 

 

배운 점

힙 자료 구조에 대해 up heap과 down heap에 대해서 배웠고 힙 자료구조의 경우 경우 시간 복잡도가 O(log N) 으로 굉장히  짧다는 것을 알게 되었다.

1. 삽입 (Insert): O(log N):
   새로운 요소를 힙에 추가할 때, 힙 속성을 유지하기 위해 log N의 시간이 걸립니다.
   
   
2. 최솟값 또는 최댓값 추출 (Extract Min/Max):
   O(1) 힙의 루트에 있는 최솟값 또는 최댓값을 추출하는 연산은 상수 시간이 걸립니다.
   
   
3. 최솟값 또는 최댓값 제거 및 재구성 (Delete and Reconstruct): O(log N):
   힙의 루트에 있는 값을 제거하고, 힙 속성을 유지하기 위해 log N의 시간이 걸립니다.
   
   
4. 힙 구성 (Build Heap): O(N):
   주어진 배열이나 리스트를 힙으로 변환하는 연산은 선형 시간이 걸립니다.
   
   
5. 힙 정렬 (Heap Sort): O(N log N):
   힙을 구성하는 데 O(N)의 시간이 걸리고, 각 요소를 추출하는 데 O(log N)의 시간이 걸리므로 전체적으로 O(N log N)의 시간이 걸립니다.