[Programmers] - 더 맵게

[Programmers] - 더 맵게

 

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=python3 

프로그래머스

 

문제 설명

---

모든 매운 지수들을 K이상으로 만든다. K보다 작은 값들은 2가지를 합쳐 스코빌을 높일 수 있다.

이 때 몇번만에 모든 스코빌 지수를 K보다 크게 할 수 있는가?

 

알고리즘

---

가장 작은 수들을 계속하여 합쳐야 함으로 우선순위 Queue 알고리즘을 사용하였다.

Heapq를 통하여 가장 작은 숫자를 O(logN)에 뽑아내어 갱신시켜주는 것이다.

 

1. Heapq에 현재 값 스코빌 지수 setting

2. 앞에서부터 처리하되 K이상이라면 종료

3. 그렇지 않다면, 앞에 2가지를 섞어 갱신 시켜준다.

4. 2~3 반복

5. 그럼에도 불구하고 K보다 작은 스코빌이 존재한다면 절대 스코빌을 만들 수 없음으로 -1로 처리

 

코드

---

#Programmers 더 맵게

import heapq

scoville = [1, 2, 3, 9, 10, 12]
K = 7

def solution(scoville, k):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville) >= 2 :
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        if first >= k and second >= k :
            break

        heapq.heappush(scoville,first+second*2)
        answer+=1

    if scoville and scoville[0] < k :
        answer=-1
    return answer

print(solution(scoville, K))