힙 Level 2 더 맵게 - python (프로그래머스)

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

프로그래머스

 

소스 코드

from heapq import heapify, heappush, heappop


def solution(scoville, K):
    
    heapify(scoville)
    count = 0
    while True:
        
        if len(scoville) <= 1:
            low_1 = heappop(scoville)
            if low_1 < K:
                count = -1
                break
            else:
                break
        else:
            low_1 = heappop(scoville)
        
    
            if low_1 >= K:
                break
            
            low_2 = heappop(scoville)
            new_scoville = low_1 + (low_2 * 2)
            heappush(scoville, new_scoville)
        
        count +=1
        
    
    return count

 

풀이

본 문제의 풀이에서는 min heap을 사용하였다. 처음 scoville 리스트를 heapify 함수를 사용하여 min heap 형태로 초기화해 주었다.

 

갱신되는 scoville 값은 min heap에 push 되므로 scoville 리스트는 항상 오름 차순으로 정렬되며 그에 따를 시간 복잡도는 O(logN)이다. 따라서 맨 처음에 scoville 리스트의 길이가 1 이하일 경우와 2 이상일 경우를 나눈 다음 값을 pop 할 때마다 값이 K 이상인지 확인을 하는 과정을 거치면 된다. 

 

while loop의 탈출 조건은 다음과 같다.

 

1. 실행 중간에 최소 값이 K 이상의 값이 나온 경우

2. 모든 연산을 하였지만 K보다 크게 나오지 못한 경우

3. 끝까지 연산한 결과 K 이상의 값이 나온 경우