문제 설명
풀이 과정 & 코드
- 해당 문제는 주어진 scoville안에 가장 작은 수가 K값 보다 작을 때 위 공식을 통해 새로운 scoville을 만드는 문제임
- 주어진 K보다 모든 scoville지수가 높아야하고 섞은 횟수를 return 하면 되는 문제임
- 리스트의 길이가 최대 1,000,000 이여서 2중 for loop을 하는 순간 시간초과가 남
- 따라서 heap queue를 사용해서 풀어야 함
- 초기에 heapq.heapify(scoville)을 해서 리스트의 앞단에는 항상 최소 값이 들어가게 만들고 이후 해당 값을 주어진 식을 통해 계산하고 다시 scoville에 추가하면 값의 크기에 따라 위치가 결정됨
- 위 방법을 계속 진행하면 주어진 scoville 지수가 전부 K값이 될 수 있는지 없는지 알게됨
- 추가로 K값 이상 만들 수 없는 경우에는 전부다 섞었지만 리스트의 길이가 결국 1이 되고 해당 값이 K보다 작은 경우 뿐임
- 탈출 조건으로 위와 같이 설정하면 원하는 값을 얻을 수 있게됨
def solution(scoville, K):
import heapq
ans = 0
heapq.heapify(scoville)
while True:
temp = 0
not_spicy1 = heapq.heappop(scoville)
if not_spicy1 < K:
not_spicy2 = heapq.heappop(scoville)
heapq.heappush(scoville, not_spicy1 + not_spicy2*2)
ans += 1
elif not_spicy1 >= K:
return ans
if len(scoville) == 1 and scoville[0] < K:
break
return -1
