더 맵게

📖 힙(Heap) > 더 맵게

• new scoville = lowest scoville + (second lowest scoville *2)

📖What I thought

• 가장 작은 값을 찾아 스코빌지수가 k보다 작은지 확인해야 함
• 가장 작은 값을 계속 찾으려면? 최소힙
• heapq 사용하면 항상 0번째 값이 최솟값 → 뉴 스코빌 지수 만들어서 값 추가해도 최솟값 새로 구할 필요 없어 → 최솟값에 접근 쏘 이지
• 뉴 스코빌 지수를 만드는 최대 횟수는 == 만들다 만들다 값이 1개만 남게 되는 경우 → n-1번 뉴 스코빌 지수 만들기 과정 진행 for문은 n-1번 돌면 됨

📖풀이

📎heapq

import heapq
 
def solution(scoville, K):
    heapq.heapify(scoville)
    
    cnt = 0
    for _ in range(len(scoville)-1):
        if scoville[0] < K:
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville)*2)
            cnt += 1
        else:
            return cnt
        
    if scoville[0] >= K:
        return cnt
    else:
        return -1

• 0번째 값(최솟값)이 k보다 크다면 다른 값들은 모두 만족 → 섞은 횟수 return
• 값을 다 합쳐서 원소가 1개만 남으면 for문 탈출 → for문 나와서 마지막으로 k보다 큰지 체크

📖What I learned

1. 파이썬에서 우선순위 큐를 사용할 때 heapq 모듈을 활용한다!

📖관련 지식

📎Priority Queue

📎Heapq