반응형
문제
https://programmers.co.kr/learn/courses/30/lessons/42626
풀이
import heapq
def solution(scoville, k):
heapq.heapify(scoville)
i = 0
while scoville[0] < k:
if len(scoville) > 1:
heapq.heappush(scoville, heapq.heappop(
scoville) + (heapq.heappop(scoville) * 2))
i += 1
else:
return -1
return i
- 단순 queue 혹은 stack으로는 새로 생성되는 값(섞은 음식의 스코빌 지수)를 정렬하기 어렵다
- heapq 활용 : 우선순위대로 자동정렬해주는 자료구조 (우선순위 큐)
- heapq.heapify(list) : 자료구조 heap화
- heapq.heappush(heap, item) : 힙 구조를 유지하면서 값 삽입
- heapq.heappop(heap) : 가장 작은값 반환
- scoville[0]은 scoville에서 가장 작은 값이다. 해당 값이 k보다 작은 이상 계속해서
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
를 반복한다. - 만약 scoville의 크기가 1인데 그것이 k보다 작은 스코빌 지수를 가진다면 불가능한 것이므로 -1를 반환한다.
반응형
'💻 CS > 알고리즘 연습' 카테고리의 다른 글
[알고리즘 연습] 타겟 넘버 (프로그래머스 lv2, 파이썬) (0) | 2021.06.10 |
---|---|
[알고리즘 연습] 수식최대화 (프로그래머스 lv2, 파이썬) (0) | 2021.06.10 |
[알고리즘 연습] 124나라의 숫자 (프로그래머스 lv2, 파이썬) (0) | 2021.06.09 |
[알고리즘 연습] 실패율 (프로그래머스 lv1, 파이썬) (0) | 2021.06.08 |
[알고리즘 연습] 체육복 (프로그래머스 lv1, 파이썬) (0) | 2021.06.07 |