✏️ 문제설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
⛔️ 제한사항
- scoville의 길이는 2 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
🎈 입출력 예
- scoville = [1, 2, 3, 9, 10, 12]
- K = 7
- return = 2
- 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
- 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
- 가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]- 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
- 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
- 가진 음식의 스코빌 지수 = [13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
👩💻 내 코드
이전에 백준 문제 중 최소힙과 최대힙 문제를 푼 적이 있었는데 그 때 당시 파이썬 라이브러리 heapq를 이용해서 구현했었다.
덕분에 이번 문제는 조금 수월하게 해결할 수 있었다.
일단 힙 문제인건 알고 있었지만 왜 힙을 이용해서 풀어야 하는지 아는 것도 중요하다고 생각했다.
문제를 보면 가장 작은 값과 두번째 값을 이용해 계산해야하기 때문에 최솟값 연산을 빠르게 하는 힙이 가장 적합하다고 생각했다.
구현 방법을 짧게 요약하자면,
- scoville 배열을 heapify를 이용해 힙 배열로 만들어준다.
- scoville는 최소힙이 되었기 때문에 인덱스 0번째 원소가 루트이면서 가장 작은 값이 된다.
때문에 scoville[0]이 K보다 작은 경우에만 While문이 돌아가도록 한다.- heappop은 가장 작은 원소를 반환하고 기존 배열에서 삭제하기 때문에 heappop을 이용해 새로운 스코빌지수를 계산한다.
- 모든 스코빌지수를 K 이상으로 만들 수 없는 경우는 scoville 배열의 길이가 1이 되고 그 원소의 값 또한 K보다 작게 된다.
import heapq
def solution(scoville, K):
heapq.heapify(scoville) # heapqify를 이용해 배열을 힙 구조로 만들어줌
count = 0
while (scoville[0] < K): # scoville은 이제 힙 배열이기 때문에 idx 0번째 원소가 루트이면서 가장 작은 값
new = heapq.heappop(scoville) + heapq.heappop(scoville)*2
heapq.heappush(scoville, new)
count += 1
if len(scoville) <= 1 and scoville[0] < K:
count = -1
break
return count파이썬은 정말 좋은 언어인 것 같다. 다양한 라이브러리를 제공해줘서 빠르고 쉽게 코드를 구현할 수 있는 것 같다.
알고리즘이 약한 나에겐 더 좋은 언어...ㅎㅎ
물론 다른 언어로도 구현해보면서 복잡한 계산도 해야되겠지..ㅠ_ㅠ
초심 잃지 말기 🙂