문제

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

나의 코드

"""
1. 아이디어

2. 시간복잡도

"""

import heapq

def solution(scoville, K):
    
    cnt = 0 # 섞어야 하는 횟수
    
    """ 데이터가 정렬 되지 않은 상태로 들어올 수 있으므로 정렬해줘야함. 
    (안해줘서 테스트 몇개가 틀렸었음) """
    scoville.sort()
    
    heapq.heapify(scoville) # 리스트를 힙으로 변환 : O(n)
    
    while True:
        
        # 리스트의 최소값이 원하는 스코빌 지수보다 낮고 원소가 2개이상 있을 때
        if scoville[0] < K and len(scoville) > 1:
            x = heapq.heappop(scoville)
            y = heapq.heappop(scoville)

            res = x + y * 2

            heapq.heappush(scoville, res)
            
            cnt += 1
        
        # 리스트의 최소값이 원하는 스코빌 지수보다 높거나 원소가 2개 미만일때 break됨
        else:
            break
    
    # return -1이 되는 경우는 최종 원소중에 최소값이 원하는 스코빌 지수보다 낮은 경우임.
    if scoville[0] < K:
        return -1
    else:
        return cnt
    

설명

• 파이썬 에서의 힙(Heap)
  
  heapq 모듈에는 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다. 자바의 PriorityQueue 클래스처럼 리스트와 별개의 자료구조가 아닌 점에 유의해야 합니다.
  
  그렇기 때문에, 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 합니다. 다시말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙입니다.

• 힙(Heap) 변환
  heapify() 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 위에서 다룬 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 위치됩니다. 즉, 비어있는 리스트를 생성한 후 heappush() 함수로 원소를 하나씩 추가한 효과가 납니다. heapify() 함수의 성능은 인자로 넘기는 리스트의 원소수에 비례합니다. 즉 O(N)의 시간 복잡도를 가집니다.

• 파이썬 에서의 힙 원소 추가, 삭제
  
  heappush() 함수는 O(logN)의 시간 복잡도를 가집니다.
  또한 heappop() 함수도 O(logN)의 시간 복잡도를 가집니다.

• 최소값을 얻을 때 주의 사항
  
  힙에서 최소값을 삭제하지 않고 단순히 읽기만 하려면 일반적으로 리스트의 첫번째 원소에 접근하듯이 인덱스를 통해 접근하면 됩니다.
  
  여기서 주의사항은 인덱스 0에 가장 작은 원소가 있다고 해서, 인덱스 1에 두번째 작은 원소, 인덱스 2에 세번째 작은 원소가 있다는 보장은 없다는 것입니다. 왜냐하면 힙은 heappop() 함수를 호출하여 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 인덱스 0에 위치시키기 때문입니다.
  
  따라서 두번째로 작은 원소를 얻으려면 바로 heap[1]으로 접근하면 안되고, 반드시 heappop()을 통해 가장 작은 원소를 삭제 후에 heap[0]를 통해 새로운 최소값에 접근해야 합니다.

다시 풀이한 코드

import heapq

def solution(scoville, K):
    
    # scoville.sort() 
    # 처음 풀이했을 때 이 구문 필요하다고 했는데 다시 풀어보니 사실상 필요없음. 
    # 이유) 정렬의 유무와 상관없이 어차피 반복문 내에서 필요한건 최솟값 뿐이다.
    # heappop()을 통해 최솟값을 꺼내면 항상 최소 힙 형태로 다시 정렬된다.
    
    heapq.heapify(scoville) # 리스트를 힙으로 변환 : O(n)
    cnt = 0
    
    while True:
        
        # 스코빌 지수가 가장 적은 것이 K보다 크거나, 음식 개수가 2개 미만일때 break
        if scoville[0] >= K or len(scoville) < 2:
            break
        
        """ 음식 개수가 2개 이상일 때 [ 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 
        스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) ] 해주면 됨. """
        if len(scoville) >= 2:
            rs = heapq.heappop(scoville)
            rs2 = heapq.heappop(scoville)
            heapq.heappush(scoville, rs + rs2 * 2)
            
        cnt += 1
    
    # 스코빌 지수가 가장 작은 값이 K이상이면 cnt를, 그렇지 않으면 -1을 return
    if scoville[0] >= K:
        return cnt
    else:
        return -1
        

참고 자료

https://www.daleseo.com/python-heapq/
https://hocheon.tistory.com/70