[레벨2][파이썬] 더 맵게

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

프로그래머스

 

1차 시도: sorted, pop을 이용한 풀이 → 효율성 테스트 실패

def solution(scoville, K):
    answer = 0
    sorted_scoville = sorted(scoville)

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

        a = sorted_scoville.pop(0)
        b = sorted_scoville.pop(0)
        r = a + (b * 2)
        sorted_scoville.append(r)
        sorted_scoville.sort()
        answer += 1

    return answer

 

2차 시도: heapq 모듈 이용한 풀이 → 성공

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)  # 스코빌 지수를 최소 힙으로 변환

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

        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        r = a + (b * 2)
        if r >= K:
            check += 1
        heapq.heappush(scoville, r)  # 새로운 스코빌 지수를 힙에 추가
        answer += 1

    return answer

 

1) heapify() 함수를 사용하면 최솟값이 맨 앞에 위치하게 되므로 반복문 내에서 최솟값을 추출할 때 heappop() 함수를 사용합니다.

2) 힙에 추가할 때 heappush() 함수를 사용하여 자동으로 정렬된 상태를 유지합니다.