Level 2. 더 맵게

08. 더 맵게

코딩테스트 연습 > 힙(Heap) > 더 맵게
https://programmers.co.kr/learn/courses/30/lessons/42626

---

문제 설명

Input value =

• scoville = 정렬되어 있지 않은 양의 정수 리스트

• K = 목표로 하는 값

Process =

• $y = x_1 + x_2 * 2$

Output =

• scoville의 원소가 모두 K 이상이 되기 위해 행한 Process수행 횟수

---

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.

• K는 0 이상 1,000,000,000 이하입니다.

• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

---

문제 구상

heap을 이용

#00
scoville = [1,2,3,9,10,12]
K = 7
#01
from heapq import heappush,heappop, heapify
s = []
for i in scoville:
    heappush(s,i)
cnt = 0
#02
while s[0]<K:
    try:
        heappush(s,heappop(s)+heappop(s)*2)
    except IndexError:
        -1
    cnt+=1
#03
cnt

sorted(list, reverse=True)를 이용

시간초과!

#00
scoville = [1,2,3,9,10,12]
K = 7
#01
s = sorted(scoville,reverse=True)
cnt = 0
while s[-1]<K:
    try:
        s[-2]=s[-2]*2+s[-1]
        s.pop()
        s = sorted(s,reverse=True)
    except IndexError:
        print(-1)
    cnt+=1
cnt

---

문제 풀이

from heapq import heappush,heappop, heapify

def solution(scoville,K):
    s = []
    for i in scoville:
        heappush(s,i)
    cnt = 0
    while s[0]<K:
        try:
            heappush(s,heappop(s)+heappop(s)*2)
        except IndexError:
            return -1
        cnt+=1
    return cnt