03-01 더 맵게_Heap

문제 설명

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만들음

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

---

풀이

* 섞여서 새로 만들어진 음식이 생길 때마다 음식의 스코빌 지수가 재정렬 되어야 함 (스코빌 지수가 낮은 음식 2개를 뽑아낼 필요 때문)

-> 매번 정렬 하면 효율성이 떨어짐 

Worst Case : 음식이 하나 남을 때까지 (n-1) 회 * O(n) = O(n^2)

== 힙을 사용해야 성능 개선 가능

 

Heap

max heap - 최대 원소를 먼저 뽑을 수 있음/ min heap  - 최소 원소를 먼저 뽑을 수 있음

-  최소/최대 원소를 빠르게 찾을 수 있음 

힙만들기 - heapify : O(NlgN)

삽입 - insert / 삭제 - remove : O(lgN)

✅ 모든 스코빌 지수가 K이상이 되었거나

✅ 다 섞어도 K가 안되면 Loop 종료

---

내 풀이

힙 문제라는걸 먼저 파악한 후에 코딩테스트를 수행했음

- 첫번째 시도..

import heapq

def solution(scoville, K):      # 음식의 스코빌 지수를 담은 배열, 기준 스코빌 지수
    answer = 0
    
    if sum(scoville) < K :      # 리스트값 다 더해도 K가 안되면 불가능 
        return -1 

    heapq.heapify(scoville)     # 스코빌 지수를 힙으로 변환    

    while len(scoville) >= 2:
        # 섞을 음식 힙에서 삭제하면서 스코빌 지수 가져옴
        min_scoville = heapq.heappop(scoville)  # 가장 맵지 않은 음식의 스코빌 지수
        sec_scoville = heapq.heappop(scoville)  # 두번째 스코빌 지수
        
        if min_scoville >= K and sec_scoville >= K:   # 둘다 이미 K 이상이면 섞지 않음
            break

        # 섞은 음식의 스코빌 지수 삽입
        mix_scoville = min_scoville + (sec_scoville * 2)    # 가장 맵지 않은 음식 + (두번째 스코빌 지수 * 2)
        heapq.heappush(scoville, mix_scoville)      # 새로운 음식 추가
        answer += 1                                 # 섞은 횟수 증가   
            

    return answer       # 모든 음식의 스코빌 지수를 K이상으로 만들기 위한 섞는 횟수 최소값

테스트 데이터 를 찾는게 문제다

-> solution([1, 2], 5) 의 결과값이 -1 일 거라고 생각하고 풀고 있어서 계속 틀리는 거였다

solution([1, 2], 5) 의 결과값은 1이다 (1 + 2 * 2 = 5)

import heapq

def solution(scoville, K):      # 음식의 스코빌 지수를 담은 배열, 기준 스코빌 지수
    answer = 0                  # 모든 음식의 스코빌 지수를 K이상으로 만들기 위한 섞는 횟수 최소값
    
    heapq.heapify(scoville)     # 스코빌 지수를 힙으로 변환    

    while scoville[0] < K and len(scoville) > 1:
        # 섞을 음식 힙에서 삭제하면서 스코빌 지수 가져옴
        min_scoville = heapq.heappop(scoville)  # 가장 맵지 않은 음식의 스코빌 지수
        sec_scoville = heapq.heappop(scoville)  # 두번째 스코빌 지수
        
        if min_scoville >= K and sec_scoville >= K:   # 둘다 이미 K 이상이면 섞지 않음
            break

        # 섞은 음식의 스코빌 지수 삽입
        mix_scoville = min_scoville + (sec_scoville * 2)    # 가장 맵지 않은 음식 + (두번째 스코빌 지수 * 2)
        heapq.heappush(scoville, mix_scoville)      # 새로운 음식 추가

        answer += 1                                 # 섞은 횟수 증가   
    
    return answer if scoville[0] >= K else -1

- 리스트의 sum을 확인해 계산 가능 불가능을 체크했던 부분을 삭제하고, 최종 스코빌 힙에서 최소 값이 K보다 작으면 -1을 리턴하여 계산이 불가능함을 리턴해줬다

굿이다.