문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Python
복사
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
•
scoville의 길이는 2 이상 1,000,000 이하입니다.
•
K는 0 이상 1,000,000,000 이하입니다.
•
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
•
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
예시
정답
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # 힙 구조로 만듦
while (len(scoville) >=2):
if scoville[0] >= K: # 가장 작은 값
return answer
else:
min_s = heapq.heappop(scoville) # 제일 작은 값 pop
min_s2 = heapq.heappop(scoville) # 그 다음 작은 값 pop
heapq.heappush(scoville, min_s + min_s2*2) # 힙 리스트에 새로운 값 저장
answer += 1
if scoville[0] >= K:
return answer
else:
return -1
Python
복사
풀이
•
전형적인 힙 문제이다.
•
문제 자체는 어렵지 않다. 리스트에서 스코빌 지수가 제일 작은 값을 기준값과 비교해서 더 작으면 섞어주고 아니면 지금까지 섞은 횟수를 출력하면 된다.
•
그런데 문제는 효율성이다.
•
매번 제일 작은 값을 index를 통해서 찾고 pop을 하게 되면 시간이 굉장히 오래걸린다. 따라서 우리는 힙 리스트를 사용한다.
•
힙은 제일 작은 값을 맨 앞으로 보내는 자료 구조이다. 따라서 기존의 스코빌지수 리스트를 우선 힙 자료구조로 변환한다.
import heapq
heapq.heapify(scoville) # 힙 구조로 만듦
Python
복사
•
힙 구조로 만들면 가장 작은 값이 맨 앞으로 이동하기 때문에 우리는 맨 앞의 값만 K보다 큰지 작은지를 확인하면 된다.
if scoville[0] >= K: # 가장 작은 값
return answer
Python
복사
•
힙 구조에서 제일 작은 값을 pop 하려면 heapq.heappop()함수를 사용하면 된다.
min_s = heapq.heappop(scoville) # 제일 작은 값 pop
min_s2 = heapq.heappop(scoville) # 그 다음 작은 값 pop
Python
복사
•
그 다음 새로운 값을 힙 리스트에 저장하려면 heapq.heappush() 함수를 사용한다. 이때 저장되는 값은 바로 정렬이 되기 때문에 새로 또 정렬을 수행할 필요가 없다.
heapq.heappush(scoville, min_s + min_s2*2) # 힙 리스트에 새로운 값 저장
Python
복사
•
나머지는 문제 조건에 맞게 제일 작은 값이 K 이상이거나 더이상 올릴 수 없을 때까지 (스코빌 지수 리스트에서 1개만 남았을 때) 반복하면 된다.