|
์ฝ๋ ์์ฑํ๊ธฐ
import heapq
def solution(scoville, K):
answer = 0
heap = []
for i in scoville:
heapq.heappush(heap, i)
# print(heap)
while heap[0] < K:
if len(heap) == 1:
return -1
a = heapq.heappop(heap)
b = heapq.heappop(heap)
hot = a + 2*b
heapq.heappush(heap, hot)
# print(f"a={a}, b={b}, hot={hot}, heap={heap}")
answer += 1
return answer
Python
๋ณต์ฌ
|
์ฝ๋ ์ค๋ช
ํ๊ธฐ
heap์ ์ฐ์ ์์ ํ๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ํ๋ค.
1.
์ฐ์ ์์ ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ํ์ฉํ heap ๋ฆฌ์คํธ๋ฅผ ๋ง๋ ๋ค.
2.
๋ชจ๋ ์ค์ฝ๋น ์ง์๊ฐ K๋ฅผ ๋์ง ์์ผ๋ฉด(heap์ ๊ธธ์ด๊ฐ 1์ผ๋) -1์ผ ๋ฐํ
3.
์ ์ผ ์์ ์ a, ๊ทธ๋ค์ ์์ ์ b๋ฅผ ์ง์ ํ์ฌ ์์ ์์์ ์ค์ฝ๋น ์ง์ hot ๋ณ์๋ฅผ ๋ง๋ ๋ค.
4.
hot์ heap์ ๋ฃ๋๋ค.
5.
๊ฐ์ 1์ ์ถ๊ฐํ๋ค.