[heap] 더 맵게 (프로그래머스, Level 2)

Soorim Yoon·2022년 9월 24일

heap 코테

알고리즘 & 코딩테스트

목록 보기

27/67

문제

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

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 함수를 구현해라.

풀이

추후 보완 예정

코드

처음 코드 (시간 초과)

import heapq
def solution(scoville, K):
    heap = []
    for i in scoville:
        heapq.heappush(heap, i)     # heap 배열을 생성해서 heapq를 사용해 배열 속에 스코빌배열 안의 요소들을 모두 집어넣는다. (자동으로 오름차순으로 저장된다)
    
    count = 0
    while(1):      # heap[0]값 (=최솟값)이 K보다 작은 동안, heap 배열의 요소 개수가 1개 이상인 경우만 실행
        min1 = heapq.heappop(heap)
        min2 = heapq.heappop(heap)
        val = min1+min2*2
        heapq.heappush(heap, val)
        count += 1
        
        if len(heap) == 1 or heap[0] > K:     # => 여기서 시간 초과 발생
            break
    
    if heap[0] > K:
        return count
    else:
        return -1

💡 시간 초과 발생 이유

heap[0]과 heapq.heappop(heap) 모두 heap 배열에서 가장 작은 요소를 가리키는 방법이다
하지만 heapq.heappop(heap) 연산은 heap[0]을 통해 값을 지칭하는 것보다 오랜 시간이 소요된다. (값을 빼줘야하기 때문에 단순히 값을 지칭하는 것과는 시간 차이가 존재)
따라서 값의 대소 비교만 하는 경우에는 pop을 해주지 않고 해당 요소를 가리켜 값을 확인해야 한다.

정답 코드 (시간 초과 해결)

heapq.heappop(heap)을 통해 가장 작은 값을 뽑아 K 값과 비교해줬던 것을, heap[0] 요소를 지칭하여 해당 값과 K 값을 비교해주니 시간 초과 에러가 해결됐다.

import heapq

def solution(scoville, K):
    heap = []
    for i in scoville:
        heapq.heappush(heap, i)     # heap 배열을 생성해서 heapq를 사용해 배열 속에 스코빌배열 안의 요소들을 모두 집어넣는다. (자동으로 오름차순으로 저장된다)
    
    count = 0
    while heap[0] < K and len(heap) > 1:      # heap[0]값 (=최솟값)이 K보다 작은 동안, heap 배열의 요소 개수가 1개 이상인 경우만 실행
        min1 = heapq.heappop(heap)
        min2 = heapq.heappop(heap)
        val = min1+min2*2
        heapq.heappush(heap, val)
        count += 1
    
    if heap[0] > K:
        return count
    else:
        return -1