더 맵게

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42626

❔ 문제 설명

매운 것을 좋아하는 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 합니다.

---

💡 풀이 (언어 : Java & Python)

힙이라는 자료구조를 이용하면 쉽게 풀 수 있는 문제이다. 자바에서는 heap을 PriorityQueue를 이용해서 구현하는 것을 알았다. 배열의 원소들을 큐에 모두 넣어주어 오름차순으로 정렬해주고, 맨 앞의 원소가 기준인 K이상이 될 때까지 첫번째, 두번째 원소를 섞어주고 다시 큐에 넣어준다. 반복문을 나오고 다시 맨 앞의 원소를 체크해서 K 이상이면 횟수를 반환하고, 미만이면 만들수 없는 경우로 -1을 반환한다.

Java

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int count = 0;
        for (int s : scoville)
            heap.offer(s);
        while (heap.peek() < K && heap.size() > 1) {
            int mixed = heap.poll() + (heap.poll() * 2);
            heap.offer(mixed);
            count++;
        }
        return (heap.peek() >= K) ? count : -1;
    }
}

Python

import heapq

def solution(scoville, K):
    # 리스트를 heap으로 만들어준다
    heapq.heapify(scoville)
    count = 0
    for i in range(len(scoville)-1):
        # heap에서 가장 작은, 그 다음으로 작은 원소를 추출
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        # 조건 체크
        if first >= K and second >= K:
            break
        # 섞어주고 힙에 넣어주고 카운팅. 자동으로 정렬된다.
        heapq.heappush(scoville, first + second * 2)
        count += 1
    # 힙에 원소가 없는 상태면 마지막 두 원소가 if break에 걸린 것 = 조건 만족
    # 길이가 0이면 에러 뜨는 것 방지, 마지막 원소가 k보다 작으면 조건 불만족 
    if len(scoville) != 0 and scoville[-1] < K:
        return -1
    
    return count