반응형
코딩테스트 연습 - 더 맵게
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같
programmers.co.kr
풀이
최소힙을 사용하여 해결할 수 있다. 최소힙에서 두 개를 pop해서 문제에서 주어진 식대로 계산하여 다시 힙에 넣어주면 된다. 이때 첫번째로 꺼낸 값이 K이상이면 나머지 값도 전부 K이상이라는 의미이므로 진행을 중단한다.
마지막에 한 번 더 heap에서 값을 꺼내어 해당 값이 K 이상인가를 체크했는데 이는 마지막으로 heap에 두 개의 값이 남아있고 해당 값을 주어진 식대로 계산하여 K이상을 만족하게 됐을 때를 체크 하기 위해 추가하였다.
코드
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while len(scoville) >= 2:
first = heapq.heappop(scoville)
if first >= K:
break
second = heapq.heappop(scoville)
heapq.heappush(scoville, first + second*2)
answer += 1
minScoville = heapq.heappop(scoville)
if minScoville >= K:
return answer
else:
return -1
반응형
'Algorithm > Programmers' 카테고리의 다른 글
[고득점 Kit(힙)] 이중우선순위큐 (Python) (0) | 2022.01.29 |
---|---|
[고득점 Kit(힙)] 디스크 컨트롤러 (Swift, Python) (0) | 2022.01.28 |
[고득점 Kit(해시)] 베스트앨범 (Swift, Python) (0) | 2022.01.26 |
[고득점 Kit(해시)] 위장 (Swift, Python) (0) | 2022.01.24 |
[고득점 Kit(해시)] 전화번호 목록 (Python) (0) | 2022.01.22 |
댓글