[프로그래머스] 힙(Heap) - 더 맵게 (Python3, 파이썬)

1. 문제

문제 요약

•  '몇번' 섞어야 Leo가 원하는 스코빌 지수 이상의 음식만 배열에 남는지 출력하자.
•  주어지는 값 : Leo가 가진 음식의 스코빌 지수를 담은 배열, 원하는 스코빌 지수 K
•  사용되는 공식 : 섞은 음식의 스코빌 지수 = 제일 작은 스코빌 지수 + 두 번째로 작은 스코빌지수 x 2

 

2. 입출력 예시와 설명

 

3. 코드

- 내가 시도한 코드

테스트 케이스는 통과했지만 정답은 아니었다.

정확률 50%였다... 효율성 테스트는... 빠르게 다른 사람의 코드를 참고해보자.

 

- 정답 코드 (참고한 코드)

 

import heapq

def solution(scoville, k):
    heap = []
    for i in scoville:
        heapq.heappush(heap, i)

    answer = 0
    while heap[0] < k:
        try:
             heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        answer += 1
    return answer

 

힙 자료구조를 사용한 코드이고, 파이썬의 heapq 내장 모듈을 사용한 코드이다.

heappush 함수로 heap에 값을 추가할 수 있고, heappop 함수로 heap에서 값을 제거할 수 있다.

heapify 함수로 리스트를 힙으로 만들 수도 있다.

* 파이썬의 heapq에서는 최소힙만 지원된다. 

 

또 이 분의 코드에서 배울 점은 try except 문을 사용해 예외처리를 했다는 점 같다.

문제를 해결하는데만 집중하여 예외처리를 잊을 때가 많은데 앞으로 잘 기억해야겠다.

 

참고 링크 : https://itholic.github.io/kata-more-spicy/