프로그래머스 Lv.2 | Python | 더 맵게

1. 문제 정보

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

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

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

---

3. 접근 기준

• 모든 음식의 스코빌 지수가 K 이상이 될 때까지, 가장 맵지 않은 두 음식을 반복적으로 섞어야 한다.

매번 가장 작은 값을 빠르게 꺼내어 섞는 과정을 반복하는 방식으로 접근한다

---

4. 사용한 패턴 / 알고리즘

• 최소 힙(min-heap)
  • 매번 최솟값 2개를 빠르게 꺼내야 하는 구조
  • 정렬을 반복하는 대신 heap을 사용하여 효율적으로 처리

“가장 작은 값을 반복적으로 선택해야 하는 상황에서 heap을 활용하는 방식”

---

5. 핵심 아이디어

• 최소 힙을 사용해 가장 작은 두 값을 지속적으로 추출
• 두 값을 섞어 새로운 값을 만들고 다시 힙에 삽입
• 최솟값이 K 이상이 될 때까지 반복
• 더 이상 섞을 수 없는데 조건을 만족하지 못하면 -1 반환

---

6. 풀이 코드

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    answer = 0
    while True:
        if scoville[0]>=K:
            return answer
        if len(scoville)==1:
            return -1
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)

        result = first + (second*2)

        heapq.heappush(scoville, result)
        answer+=1
    return answer

---

7. 핵심 로직 요약

1. 최소 힙을 사용하여 2번 pop 한다.
2. 해당 값들을 스코빌 지수 공식에 대입하여 다시 scoville에 추가하여 heapq를 사용하여 재정렬한다.
3. 위 방식을 가장 작은 값이 K이상일 때 까지 반복한다.

---

8. 어려웠던 점

• heapq를 처음 접하는 문제였다. 단순히 리스트의 재정렬을 반복하는 것이 아닌 heapq의 특징을 활용하여 푸는 연습을 계속해서 진행하도록 하자.

---