99클럽 코테 스터디 25일차 TIL + 오늘의 학습 키워드 : 힙

항해25일차
프로그래머스 -

이 문제는 주어진 스코빌 지수를 가진 음식들을 섞어서 모든 음식의 스코빌 지수를 K 이상으로 만드는 최소 횟수를 구하는 문제입니다. 이를 해결하기 위해 우선 스코빌 지수가 가장 낮은 두 개의 음식을 선택하고, 그 두 음식을 섞어서 새로운 음식을 만들어야 합니다. 이 과정을 반복하여 모든 음식의 스코빌 지수가 K 이상이 될 때까지 진행합니다.

이 문제를 해결하기 위해 우선 최소 힙(min-heap)을 사용할 수 있습니다. 최소 힙을 사용하면 가장 낮은 두 개의 스코빌 지수를 효율적으로 찾을 수 있습니다. 아래는 이 문제를 해결하는 `solution` 함수의 구현입니다.

```python
import heapq

def solution(scoville, K):
    # 스코빌 지수를 최소 힙으로 변환
    heapq.heapify(scoville)
    mix_count = 0
    
    while True:
        # 가장 낮은 스코빌 지수를 가진 두 개의 음식을 꺼냄
        first = heapq.heappop(scoville)
        
        # 만약 첫 번째 음식의 스코빌 지수가 K 이상이면 종료
        if first >= K:
            return mix_count
        
        # 두 번째 음식이 없으면 -1 반환
        if not scoville:
            return -1
        
        second = heapq.heappop(scoville)
        
        # 새로운 음식의 스코빌 지수 계산
        new_scoville = first + (second * 2)
        
        # 새로운 음식을 힙에 추가
        heapq.heappush(scoville, new_scoville)
        
        # 섞은 횟수 증가
        mix_count += 1
```

설명:
1. 힙 초기화: `heapq.heapify(scoville)`를 통해 주어진 스코빌 지수를 최소 힙으로 변환합니다.
2. 반복문: 무한 루프를 통해 스코빌 지수가 K 이상이 될 때까지 반복합니다.
3. 가장 낮은 두 음식 선택: `heappop`을 사용하여 가장 낮은 두 개의 스코빌 지수를 가진 음식을 꺼냅니다.
4. 조건 확인: 첫 번째 음식의 스코빌 지수가 K 이상이면 현재까지 섞은 횟수를 반환합니다.
5. 두 번째 음식 확인: 두 번째 음식이 없으면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없으므로 -1을 반환합니다.
6. 새로운 음식 생성: 두 음식을 섞어서 새로운 스코빌 지수를 계산하고, 이를 다시 힙에 추가합니다.
7. 횟수 증가: 섞은 횟수를 증가시킵니다.

이 알고리즘은 효율적으로 작동하며, 최악의 경우에도 O(N log N)의 시간 복잡도를 가집니다.