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

문제

https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3

풀이

최소/최대 값을 계속 사용하는 알고리즘이다? –> Heap 자료구조.
파이썬 내장모듈 heapq를 통해 구현했다.
Heap 자료구조가 궁금하거나 직접 구현해야한다면
[자료구조] 힙(heap)이란 - Heee’s Development Blog를 참고하자.

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    count = 0
    
    while len(scoville) > 1 :
        scov1 = heapq.heappop(scoville)
        if scov1 >= K :
            return count
        
        scov2 = heapq.heappop(scoville)
        heapq.heappush(scoville, scov1 + scov2*2)
        count += 1
    
    return -1

# 정확성 테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.98ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.71ms, 10.2MB)
테스트 7 〉	통과 (0.60ms, 10.2MB)
테스트 8 〉	통과 (0.07ms, 10.2MB)
테스트 9 〉	통과 (0.06ms, 10.2MB)
테스트 10 〉	통과 (0.48ms, 10.2MB)
테스트 11 〉	통과 (0.30ms, 10.2MB)
테스트 12 〉	통과 (1.14ms, 10.3MB)
테스트 13 〉	통과 (0.59ms, 10.2MB)
테스트 14 〉	통과 (0.19ms, 10.2MB)
테스트 15 〉	통과 (0.76ms, 10.2MB)
테스트 16 〉	실패 (0.01ms, 10.2MB)

# 효율성 테스트
테스트 1 〉	통과 (171.57ms, 16.4MB)
테스트 2 〉	통과 (430.77ms, 22MB)
테스트 3 〉	통과 (2338.74ms, 49.9MB)
테스트 4 〉	통과 (141.67ms, 14.9MB)
테스트 5 〉	통과 (2442.48ms, 51.9MB)

엥?? 16번 테스트 케이스에 걸린다.
질문 게시판을 찾아본다.

작성자 : 백인길
scoville : [1,2,3] K : 11

이 케이스를 통과한다면 16번 통과할듯합니다..
딱맞게 K 를 통과하는 음식이 하나로 만들어지는 경우를 따지는 테스트인듯하네요.
저도 이거 때매 조금 헤메였기때문에 올려봅니다..

백인길님 감사합니다.
전혀 고려하지 못했던 경우가 존재했다.
앞서 제출한 코드를 다시 살펴보자.

    while len(scoville) > 1 :

만일 Heap에 남은 마지막 원소가 K 보다 크거나 같아지더라도
Heap의 원소개수 1에 걸려서 -1을 반환하고 있었다.
while 조건을 변경해서 제출해보자.

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    count = 0
    
    while scoville :
        scov1 = heapq.heappop(scoville)
        if scov1 >= K :
            return count
        if not scoville :
            break
        scov2 = heapq.heappop(scoville)
        heapq.heappush(scoville, scov1 + scov2*2)
        count += 1
    
    return -1

# 정확성 테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.3MB)
테스트 6 〉	통과 (0.67ms, 10.2MB)
테스트 7 〉	통과 (0.65ms, 10.2MB)
테스트 8 〉	통과 (0.07ms, 10.3MB)
테스트 9 〉	통과 (0.06ms, 10.2MB)
테스트 10 〉	통과 (0.44ms, 10.1MB)
테스트 11 〉	통과 (0.29ms, 10.2MB)
테스트 12 〉	통과 (1.03ms, 10.3MB)
테스트 13 〉	통과 (0.57ms, 10.2MB)
테스트 14 〉	통과 (0.02ms, 10.2MB)
테스트 15 〉	통과 (0.74ms, 10.2MB)
테스트 16 〉	통과 (0.01ms, 10.2MB)

# 효율성 테스트
테스트 1 〉	통과 (194.27ms, 16.3MB)
테스트 2 〉	통과 (351.77ms, 22MB)
테스트 3 〉	통과 (1691.82ms, 49.9MB)
테스트 4 〉	통과 (147.52ms, 15MB)
테스트 5 〉	통과 (1905.22ms, 51.8MB)

정확성, 효율성 모두 통과!