[Lv2.] 힙 - 더 맵게

👉 사용 언어 : PYTHON3

타겟넘버

✅ Solution

import heapq

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

 

👉 문제 설명 및 제한 사항

• 모든 음식의 스코빌 지수를 K 이상으로 만들기
• 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다❗️

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

• 매개변수 : Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville, 원하는 스코빌 지수 K
  • 2 <= scoville 길이 <= 1,000,000
  • 0 <= scoville 원소 <= 1,000,000
  • 0 <= K <= 1,000,000,000
• 리턴값 : 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1

👉 아이디어

• heapq를 이용하여 최소힙으로 구현한다.
• scoville의 최소값이 K보다 작을 동안, 그리고 scoville의 길이가 1보다 클 동안 반복문을 실행한다.
  • len(scoville) > 1 조건을 추가하지 않으면 heappop을 2번 실행할 경우에 런타임에러가 발생한다.
  • 위의 식을 이용하여 섞은 음식의 스코빌 지수를 다시 힙에 추가한다.
  • 카운트 변수 +1 한다.
  • heappush를 사용하면 정렬에 맞춰 값을 추가하기 때문에 따로 정렬 함수를 사용할 필요가 없다.
• 반복문을 다 실행한 후, scoville의 최소값이 K보다 작을 경우 -1를 리턴한다.

👉 깨달은 것 / 알게된 것

• heappush를 사용하여 힙에 값을 추가할 때, 정렬 상태를 유지하므로 별도의 정렬 함수를 사용하지 않아도 된다.

✅ heap

: 완전 이진 트리를 기본으로 한 자료구조

 

✔️ 최소힙

: heapq 모듈 이용

: 루트 노드가 가장 작은 값(= 오름차순 정렬)

• heappush(heap, item) : 힙 불변성을 유지하면서 item을 heap에 추가한다.
  
• heappop(heap) : 힙 불변성을 유지하면서 가장 작은 값을 heap에서 pop한다.
• heappushpop(heap, item) : 힙 불변성을 유지하면서 heap에 item을 넣고 가장 작은 값을 pop
  • heappush, heappop을 연달아 실행하는 것 보다 효율적인 동작❗️
• heappreplace(heap, item) : heap에 가장 작은 값을 pop 하고, 새로운 item을 push한다.
  • pop된 값이 item 보다 클 수 있으므로 경우에 따라 heappushpop과 선택하여 사용
• heapify(x) : 리스트 x를 힙 형태로 변환한다. (길이만큼의 선형시간 소요)
• heapq.merge(*iterable, key=None, reverse=False) : 여러 iterable들을 정렬해서 연결한다.
  • 모든 iterable을 메모리에 올리지 않고 제너레이터를 생성
  • 이때의 입력되는 iterable은 이미 정렬된 것으로 간주됨
• heapq.nlargest(n, iterable, key=None) : key로 주어진 함수를 기준으로 iterable에서 큰 순으로 n개를 반환한다.
• heapq.nsmallest(n, iterable, key=None) : key로 주어진 함수를 기준으로 iterable에서 작은 순으로 n개를 반환한다.
  • nlargest과 nsmallest는 n이 작을 때 효율적❗️
  • n==1 이면 min/max를 사용
  • n이 크면 sorted(iterable)을 통해 구하는게 더 효율적❗️

✔️ 최대힙

: 루트 노드가 가장 큰 값(= 내림차순 정렬)

: heap에 -item을 넣은 후 꺼내서 *(-1)한 후, 출력하면 값이 큰 순서대로 나온다.