[프로그래머스/Level2] 더 맵게 (Python)

❓ 문제

문제 설명
매운 것을 좋아하는 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 합니다.
  
  입출력 예
  입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

• 모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

🔎 문제 분석

• 어떤 자료 구조를 사용해야 할까?
  • 최악의 경우: 수가 하나 남을 때까지 섞어야 하는 경우. (n-1회)
  • 각 단계(섞는 일)에 요구되는 계산량: 정렬된 리스트에 순서 맞추어 원소 삽입. 즉, O(n)의 복잡도가 나옴.
  • O(n^2)
  • 지나치게 복잡도가 높음.
  • 그러므로 최소/최대의 원소를 빠르게 꺼낼 수 있는 자료 구조를 사용한다면 복잡도를 줄일 수 있음.
  • 힙(Heap)을 사용해야 함. 힙(Heap)은 최대/최소 원소를 빠르게 찾을 수 있음.
• 이 문제에서 사용할 수 있는 힙(Heap) 연산
  • 힙 구성 (heapify)
  • 삽입 (insert) : O(logN) heappush(삽입하고자 하는 힙, 삽입하고자 하는 원소)
  • 삭제 (remove) : O(logN) heappop(최솟값을 꺼내고자 하는 힙)

❗ 풀이

• 이 문제를 풀기 위해서는 매번 리스트 안에 있는 최솟값들을 뽑아 연산해 나가야 하기 때문에 heap을 사용해야 한다.
• 이때 사용해야 하는 힙의 연산은 무엇일까.
  • import heapq: 힙을 사용하기 위해서는 heapq를 import해야 함.
  • heapq.heapify(L): 리스트 L로부터 min heap을 구성함. (List를 힙으로 연산하기 위해 필요함.)
  • heapq.heappop(L): 리스트 L로부터 최솟값을 삭제하고, 반환함. (섞은 음식의 스코빌 수를 계산하기 위해 사용해야 함.)
  • heapq.heappush(L, x): 리스트 L에 원소 x를 삽입해 줌. (최솟값들을 통해 계산한 값을 다시 힙에 넣어 줘야 함.)
• 모든 음식의 스코빌 지수가 k 이상이 되었거나 섞을 음식이 없는데 k에 만족하지 않거나 이를 while 조건문으로 둔다.
• 또한 반복문을 돌기 전에 모든 음식의 스코빌 지수가 조건에 충족한다면 계산해 주지 않고 0을 return 해 준다.
• 혼자 풀이를 할 때는 sort를 사용해서 정렬해 주었는데 어차피 heap의 경우는 정렬을 사용하지 않아도 최솟값을 꺼내 주는 heappop 연산이 있기 때문에 scoville.sort()가 무의미한다는 것을 알았다.

import heapq

def solution(scoville, K):
    answer = 0
    # scoville.sort() 
    heapq.heapify(scoville)
    
    if all(K <= score for score in scoville):  # 스코빌 지수가 모두 K보다 크다면 while 문 자체를 돌 필요가 없으므로
        return 0							   # 0으로 반환해 준다.
    
    while(scoville):
        if len(scoville) <= 1:  #더 이상 섞을 음식이 없을 때
            if heapq.heappop(scoville) < K:   # 마지막 남은 음식의 스코빌 지수가 K보다 작다면 
                return -1					  # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없기 때문에 -1 return
            else:
                return answer
            
        a = heapq.heappop(scoville)  #첫 번째로 작은 스코빌 지수를 가진 값
        b = heapq.heappop(scoville)  #두 번째로 작은 스코빌 지수를 가진 값
        
        if a < K:
            heapq.heappush(scoville, a + (b * 2))  #제일 작은 스코빌 지수가 기준이 되는 K보다 작을 때
            answer += 1
        else:    # 제일 작은 값조차 K에 만족했기 때문에 더 이상 while문을 순환할 필요가 없음.
            break
    
    return answer

❕ 다른 사람의 풀이

• while 반복문 안에 최솟값과 두 번째 최솟값을 꺼내기 전 최솟값만을 가지고 K보다 꺼졌을 경우나 마지막 스코빌 지수일 경우에 대한 if문 처리를 해 두었다.
• 내 코드에서는 만약 스코빌 지수가 하나라도 k보다 작다면 리스트를 두 번이나 확인하는 게 되기 때문에 이 코드가 더 효율적이라고 생각했다.
• O(nlogn)의 알고리즘 복잡도를 가진다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) 
    
    while True:     
    	min1 = heapq.heappop(scoville) 
        if min1 >= K:   
        	break
        elif len(scoville) == 0:
        	answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_score = min1 + 2 * min2
        heapq.heappush(scoville, new_score)
        answer += 1
        
    return answer