[프로그래머스] [Python] Level2 - 더 맵게

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

코딩테스트 연습 - 더 맵게

풀이 유형 : 힙 Heap

1차 시도

import heapq

def solution(scoville, K):
    sum = 0
    answer = 0
    heapq.heapify(scoville)
    
    while(True):
        min1 = heapq.heappop(scoville)
        if len(scoville) == 0 : 
            answer = -1
            break
        if min1 >= K : 
            break
        min2 = heapq.heappop(scoville)
        sum = min1 + min2*2
        heapq.heappush(scoville, sum)
        answer += 1 
            
    return answer

테스트16에서 정확도 테스트 실패

2차 시도

import heapq

def solution(scoville, K):
    sum = 0
    answer = 0
    heapq.heapify(scoville)
    
    while(True):
        min1 = heapq.heappop(scoville)
        if min1 >= K : 
            break
        if len(scoville) == 0 : 
            answer = -1
            break       
        min2 = heapq.heappop(scoville)
        sum = min1 + min2*2
        heapq.heappush(scoville, sum)
        answer += 1 
            
    return answer

1차 시도에서 while반복문 안에 break를 거는 if조건의 순서를 바꿨더니 해결...

 

마지막 남은 숫자가 딱 K이상인 경우,

scoville이 0이 되어서 answer를 반환하기도 전에 끝나버리는 케이스가 16번이었나보다

💡 최종 로직 

0. scoville을 minheap으로 받는다 (root에 min값이 있고, 새로운 값을 넣어도 정렬되어 들어감 + 시간복잡도 nlogn)

0. 계산식 값을 넣을 변수를 초기화한다

1. 가장 작은 값은 받는다

  1-1. 이때 받은 값이 목표값인 K보다 크면, break

  ==> 목표도달!

  1-2. 1-1에서 break되지 않았고, scoville 길이가 0이란 뜻은 heap안에 모든 수를 계산해도 K를 넘길 수 없다는 뜻

  ==> -1을 반환하고 break

2. 두번째로 작은 값을 받는다

3. 문제에 주어진 식대로 계산하여 다시 heap에 넣는다

4. 정답으로 반환하기 위해 횟수를 count 한다