[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 더 맵게 (python)

풀이

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    try:
        while(scoville[0] < K):
            a = heapq.heappop(scoville)
            b = heapq.heappop(scoville)
            c = a + (2 * b)
            heapq.heappush(scoville, c)

            answer += 1
    except:
        answer = -1
    
    return answer

내 풀이

• 처음에 테스트 케이스 1, 3, 8, 14에서 런타임 에러가 났는데, 이는 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다." 제한 사항을 놓친 것이 원인이었다. 이는 try except문으로 구현하여 해결했다.
• heap은 파이썬에 구현된 heapq를 이용했다. 
• while문은 scoville에서 가장 작은 요소가 K보다 커질 때까지 반복하도록 했다.

 

heapq 모듈 사용법

힙

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조.
• a가 b의 부모노드이면, a의 키값과 b의 키값 사이에는 대소관계가 성립한다.
• 파이썬에서는 heapq 모듈을 제공한다.

import heapq

 

기존 배열을 heap으로 변경

arr은 heap 자료구조로 변경됨

arr = [5, 8, 7, 3, 4, 1]
heapq.heapify(arr)

 

노드 선언 및 추가

h = [] #heap 초기값
heapq.heappush(h, 8) #노드 추가
heapq.heappush(h, 4)
heapq.heappush(h, 9)

 

노드 삭제

가장 앞에 있는 노드 삭제

heapq.heappop(h) #4가 삭제됨

 

인덱스로 접근 가능

노드를 삭제하지 않고 반환할 수 있다.

print(h[0]) #8