[python] 프로그래머스 42626번 : 더 맵게 (heapq.heapify)

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

코딩테스트 연습 - 더 맵게

 

 

문제를 풀기 위해 우선 떠올려야 할 조건은 모든 음식의 스코빌 지수를 -1로 만들 수 없는 경우이다.

scoville 리스트에 원소가 하나 남았을 때,

이 값의 스코빌 지수가 k 미만인 경우 더이상 합칠 음식이 없기에 -1을 리턴해주었다. 

 

여기서 주의할 점은

heapq 사용 시 

heapq.heappop(리스트) 를 사용할 경우, 리스트가 비어있다면 index Error가 발생한다는 점

리스트를 즉각적으로 heap으로 만들고 싶은 경우 heapq.heapify(리스트) 를 사용한다는 점이다. 

 

이 아이디어를 가지고 문제를 풀어보았다.

 

import heapq

def solution(scoville, K):
    count = 0
    # scoville = sorted(scoville)
    heapq.heapify(scoville)
    while scoville:
        d1 = heapq.heappop(scoville)
        if d1 >= K:
            break
        if scoville:
            d2 = heapq.heappop(scoville)
            heapq.heappush(scoville, d1+d2*2)
            count += 1
        # d1 < K이고 scoville 리스트가 비어있다면 
        else:
            return -1
        
    return count

 

 

[틀린 풀이]

import heapq

def solution(scoville, K):
    cnt = 0
    heap = []
    for s in scoville:
        heapq.heappush(heap, s)
    while heap:
        s1 = heapq.heappop(heap)
        s2 = heapq.heappop(heap)
        if s1 < 7:
            heapq.heappush(heap, s1+s2*2)
            cnt += 1
        if s1 >= 7:
            break
    return cnt

틀린 이유 1) s2를 꺼내기 이전에 heap이 비어있는지 먼저 검사해야 함.

              2) d1 < K이고 scoville 리스트가 비어있는 경우 -1를 리턴하는 경우가 빠짐