[프로그래머스][LV.2] 더 맵게 | python3

문제링크:  더 맵게

---

문제설명

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

---

 

문제풀이

정렬을 해서 맨 앞의 두 원소로 스코빌 지수 다시 계산하고. 계산해서 나온 값을 다시 리스트에 넣어 다시 정렬을 해서 앞에 거 반복....이러면 시간초과가 날 게 분명했다.

 

근데 정렬을 하는 거 말고는 다른 방법이 떠오르지 않아서 찾아봤다.

우선순위큐, 힙을 사용하는 문제였다.

 

힙은 알아서 정렬을 해줘서 시간복잡도가 줄어든다고 한다.

하지만 난 이것들을 거의 처음 써보는 거라 공부가 필요함.

---

우선순위 큐 (Priority Queue)란?

우선순위 큐는 항상 우선순위가 가장 높은 요소를 먼저 제거할 수 있는 자료구조입니다.
이 문제에서는 최소 힙 (Min Heap) 을 사용하여 가장 작은 값부터 빠르게 꺼낼 수 있도록 합니다.

---

1. 최소 힙 (Min Heap) 구조

최소 힙은 완전 이진 트리 (Complete Binary Tree) 의 형태를 가지며,
각 부모 노드가 자식 노드보다 항상 작거나 같도록 유지됩니다.

특징

• 루트 노드(root node)는 항상 최소값이다.
• 삽입 및 삭제 연산이 O(log N) 이다.
• 힙 정렬, 다익스트라 알고리즘 등에 활용된다.

---

2. 힙 트리 구조 예제

주어진 scoville = [1, 2, 3, 9, 10, 12] 를 최소 힙 으로 변환하면 다음과 같은 트리 구조가 됩니다.

        1
       / \
      2   3
     / \   \
    9  10  12

이제, 가장 작은 두 개의 원소 1과 2를 꺼내서 새로운 값 1 + (2×2) = 5를 추가합니다.

변경 후 힙 트리

        3
       / \
      5   12
     / \
    9  10

이제 다시 3과 5를 꺼내서 3 + (5×2) = 13을 추가합니다.

최종 힙 트리

        9
       / \
      10  12
       \
       13

모든 값이 K=7 이상이므로 종료됩니다.

---

3. 우선순위 큐(힙) 삽입/삭제 과정

(1) heapq.heappush(heap, value)

새로운 값을 힙에 추가한 후, 힙 속성이 유지되도록 재정렬 합니다.
예를 들어 heap = [3, 5, 9, 10, 12] 상태에서 heapq.heappush(heap, 2)를 실행하면:

Before Insert (배열) → [3, 5, 9, 10, 12]
After Insert (배열)  → [2, 3, 9, 10, 12, 5]

트리로 보면:

       2
      / \
     3   5
    / \   \
   10  12  9

삽입 후 heapify (재정렬) 하여 부모-자식 관계를 유지합니다.

---

(2) heapq.heappop(heap)

가장 작은 값을 제거한 후, 힙 속성을 유지하도록 조정 합니다.
예를 들어, heap = [2, 3, 5, 9, 10, 12] 에서 heapq.heappop(heap)을 실행하면:

Before Pop  → [2, 3, 5, 9, 10, 12]
After Pop   → [3, 9, 5, 12, 10]

트리로 보면:

       3
      / \
     9   5
    / \
   12 10

이렇게 최소값을 제거해도 힙 속성 이 유지됩니다.

---

4. 정리

연산 설명 시간 복잡도

heapify()	리스트를 힙으로 변환	O(N)
heappush()	요소 삽입 후 재정렬	O(log N)
heappop()	최소값 제거 후 재정렬	O(log N)

 

---

함수                                                                        설명                                                                            시간 복잡도

heapq.heapify(list)	리스트를 최소 힙으로 변환	O(N)
heapq.heappush(heap, x)	힙에 값 추가	O(log N)
heapq.heappop(heap)	힙의 최소값 제거	O(log N)
heap[0]	힙의 최소값 확인	O(1)

📌 최대 힙을 사용하려면 - 부호를 붙여 활용 

 

나의코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0]<K:
        new_s=heapq.heappop(scoville)+(heapq.heappop(scoville)*2)
        heapq.heappush(scoville,new_s)
        answer+=1
        # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
        # 리스트에 원소가 1개 밖에 안남았는데 k를 넘지 못하는 경우이다.
        # 왜냐하면 원소가 2개이상이면 무조건 계산가능
        if scoville[0]<K and len(scoville)==1:
            return -1
    return answer

 

---

 

참고하기

이렇게 푸는 방법도 있다.

해당 알고리즘을 모르면 다른 알고리즘을 활용해서 문제를 풀 수 도 있어야 한다고 생각한다.

이렇게도 한 번 풀어보면 좋을듯