https://school.programmers.co.kr/learn/courses/30/lessons/42626
heap을 사용하여 문제에 접근하면 쉽게 풀 수 있다.
문제에서 요구하는 방법대로 접근하면
- 최소 스코빌 두개를 문제에서 제시한 공식을 이용하여 힙 트리에 삽입, 그리고 1회 수행할 때 마다 카운터를 추가하거나, 횟수를 알아 볼 수 있는 방법을 이용한다. (삽입연산 : O(logN) / 힙 추출 : O(1))
- 파이썬에서 제공하는 heapq는 트리 인덱스 0이 최대/최소값으로, 0번 값만 K와 비교하여 K보다 높으면 조건을 충족한다.
위의 풀이대로 해당 문제를 풀다가 테스트 케이스 18번만 틀리는 상황이었는데,
음식을 섞지 않고 기존 스코빌 점수가 이미 K값을 넘을 때 상황을 고려해야한다. 이 때는 위의 풀이 방법을 적용하지 않고 바로 0을 출력하도록 해야한다
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
if scoville[0] >= K:
return answer
while True:
if len(scoville) == 1 or len(scoville) == 0:
return -1
food1 = heapq.heappop(scoville)
food2 = heapq.heappop(scoville)
new_food = food1 + (food2 * 2)
answer += 1
heapq.heappush(scoville,new_food)
if scoville[0] >= K:
return answer
전체적인 시간복잡도는 O(N)정도로 추측하고 있다.