이 포스팅은 프로그래머스 시리즈 28 편 중 3 번째 글 입니다.
목차
풀이
가장 최소인 녀석을 계속해서 뽑아야 하기 때문에 heap 구조를 사용했다. 이 때 python으로 코딩을 하려한다면 무조건적으로 heapq를 사용할 것. priorityQueue는 속도가 너무 느려서 효율성 통과를 하지 못한다.
Code
import heapq
def solution(scoville, K):
# 가장 작은 원소를 가져온다
# 그 녀석이 K보다 큰지 파악한다.
# 아니면
# 그 다음 원소를 가져온다
# 섞는다.
# 섞은 횟수 1추가한다.
# 다시 넣는다.
# 반복한다.
q = scoville[:]
heapq.heapify(q)
count = 0
while q[0] < K and len(q) > 1: # 제일 작은 원소가 K보다 작고 들어간 개수는 2이상이면 진행
a = heapq.heappop(q)
b = heapq.heappop(q)
c = a + b * 2
heapq.heappush(q, c)
count += 1
if q[0] >= K:
return count
else:
return -1