[programmers] 프로그래머스 더 맵게(Python)

(주)그렙

[programmers] 프로그래머스 더 맵게

(Python)

(글쓴날 : 2020.06.19)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 더 맵게

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

매운 음식의 스코빌 지수라는 특정 지수가 주어질 때, 주어지는 모든 음식의 스코빌 지수를 K 이상으로 만드는 문제입니다.

 

저의 경우, 우선순위 큐를 적용하였고, Python을 사용했습니다.

스코빌 지수가 담긴 배열에 최소힙 기반의 우선순위 큐를 적용하여 스코빌 지수가 가장 작은 두 음식이 K 미만일 경우 문제에서 제시한 방법으로 섞은 뒤, 다시 우선순위 큐에 저장하고 꺼내는 것을 반복하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import heapq
 
 
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
 
    while 1:
        if len(scoville) == 1:
            if scoville[0] >= K:
                return answer
            return -1
 
        spicy1 = heapq.heappop(scoville)
        spicy2 = heapq.heappop(scoville)
 
        if spicy1 < K or spicy2 < K:
            newSpicy = spicy1 + (spicy2 * 2)
            heapq.heappush(scoville, newSpicy)
            answer += 1
        else:
            return answer

---