[프로그래머스] Heap lv2 - 더맵게

문제 링크 - (프로그래머스 웹사이트로 연결)

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

---

1차 시도

from heapq import heappop, heappush, heapify

def solution(scoville, K):
    
    heap = []
    heapify(heap)
    for sc in scoville:
        heappush(heap, sc)
    
    count = 0
    
    # 음식을 섞을 필요가 없는 경우
    if min(heap) >= K:
        return 0
    
    # 음식을 섞는 경우
    while min(heap) < K:
        min_sc = heappop(heap)
        min2_sc = heappop(heap)
        new_sc = min_sc + min2_sc*2
        heappush(heap, new_sc)
        count += 1
    
    # 섞어서 모두 K 이상으로 만드는 데에 성공했는지 판단
    if min(heap) >= K:
        return count
    else:
        return -1 

채점 결과
정확성: 57.1
효율성: 0.0
합계: 57.1 / 100.0

• 효율성 테스트에서 모두 통과하지 못했다.
• 정확성 테스트에서 일부 런타임에러로 실패했다.

2차 시도

from heapq import heappop, heappush, heapify

def solution(scoville, K):
    
    heapify(scoville) #O(n*logn)
    count = 0
    
    # 음식을 섞을 필요가 없는 경우
    if scoville[0] >= K:
        return count
    
    # 음식을 섞는 경우
    while scoville[0] < K:
        min_sc = heappop(scoville)
        min2_sc = heappop(scoville)
        new_sc = min_sc + min2_sc*2
        heappush(scoville, new_sc)
        count += 1
    
    # 섞어서 모두 K 이상으로 만드는 데에 성공했는지 판단
    if scoville[0] >= K:
        return count
    else:
        return -1 

-> 별도의 heap을 선언하는 대신 scoville 을 직접 heap으로 만들고, 가장 작은 숫자를 scoville[0] 으로 구했다.

채점 결과
정확성: 65.4
효율성: 19.2
합계: 84.6 / 100.0

여전히 몇몇 케이스에서 런타임 에러가 발생했다.

3차 시도

from heapq import heappop, heappush, heapify, nsmallest

def solution(scoville, K):
    
    heapify(scoville) #O(n*logn)
    count = 0
    
    # 음식을 섞을 필요가 없는 경우
    if scoville[0] >= K:
        return count
    
    # 음식을 섞는 경우
    while scoville[0] < K:   # 모두 K이상이면 while문 탈출
        min_sc = heappop(scoville)
        min2_sc = heappop(scoville)
        new_sc = min_sc + min2_sc*2
        heappush(scoville, new_sc)
        count += 1
        
        # 섞어서 모두 K 이상으로 만드는 데에 성공했는지 판단
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        
    return count

2차 시도의 문제점:

while문에 별도의 탈출 조건이 없어, scoville 리스트에서 요소가 하나 남았을 때까지 끝까지 진행하게 되면 heappop을 연속으로 두 번 실행할 때 오류가 발생할 수 있다.

해결 방법:

다른 사람의 풀이를 참고해서 while문 안에 if문을 넣어, while문 실행 도중 return -1 하는 경우를 별도로 지정해주었다. 이렇게 하면 while문을 끝까지 돌지 않아도 if문을 만족할 때 바로 while문을 탈출할 수 있으며, 더 이상 pop할 요소가 없어 runtime error가 나는 것을 방지할 수 있다.

→ 정확성, 효율성 테스트 모두 통과

TIL: Today I Learned

• while문 안에 if문을 넣어서 예외처리를 할 수 있다. (필요하다면) 오히려 그 편이 불필요한 실행시간을 줄여 효율성 테스트에서 도움이 될 수 있다.
• heapq로 만든 min heap의 최솟값은 해당 리스트의 첫번째 요소이다.
• heapify의 시간복잡도는 O(n*logn)이다.