사용한 풀이법 : heap
풀이 과정
최소값과 그 다음값을 탐색, 계산 후 다시 삽입 => 해당 연산이 조건을 충족할 때 까지 반복되어야 함.
이를 위한 자료구조가 바로 최소힙!
1. heapify 메서드를 통해 scoville 리스트를 최소힙으로 초기화
2. 항상 최소값을 뽑아내는 heappop 연산을 통해 min1, min2를 설정
이때, min1이 k이상이거나, 더 이상 뽑아낼 원소가 없을때는 반복문 종료
3. 삽입할 원소를 계산 후, 힙에 push
4. 연산이 완료 될 때마다 +1한 answer를 리턴
풀이 코드
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while True:
min1 = heapq.heappop(scoville)
if min1 >= K:
break
elif len(scoville) == 0:
answer = -1
break
min2 = heapq.heappop(scoville)
new = min1 + min2*2
heapq.heappush(scoville, new)
answer += 1
return answer
'알고리즘' 카테고리의 다른 글
[자료구조] 해시 & 그리디 (0) | 2024.03.28 |
---|---|
[자료구조] 이진 트리 & 힙 (0) | 2024.03.27 |
[자료구조] 연결 리스트 & 스택 (0) | 2024.03.26 |
백준 #1912 <연속합> 파이썬 (0) | 2024.03.12 |
백준 #1699 <제곱수의 합> (0) | 2024.03.09 |