[LeetCode 75] Medium - 2462. Total Cost to Hire K Workers

2462. Total Cost to Hire K Workers

 

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)  # 근로자의 총 수
        
        # **교차점 처리**:
        # 만약 앞부분(pre)과 뒷부분(suf)이 겹치는 경우:
        # 전체를 정렬한 뒤, k명의 최소 비용을 더한 값을 반환.
        if 2 * candidates + k > n:
            costs.sort()  # 비용 정렬
            return sum(costs[:k])  # k개의 최소값을 반환

        # **초기화**:
        # 앞부분 후보(pre)와 뒷부분 후보(suf)를 각각 힙으로 변환
        pre = costs[:candidates]  # 앞부분에서 최대 candidates 개수 추출
        suf = costs[-candidates:]  # 뒷부분에서 최대 candidates 개수 추출
        heapify(pre)  # 최소 힙으로 변환
        heapify(suf)  # 최소 힙으로 변환

        i, j = candidates, n - 1 - candidates  # pre와 suf 사이의 남은 인덱스 관리
        res = 0  # 최종 비용 초기화

        # **k번 반복**: k명의 근로자 고용
        for _ in range(k):
            # **비용 비교 및 선택**:
            # pre와 suf의 최소값 중 더 작은 값을 선택
            if pre[0] <= suf[0]:
                # pre에서 최소값을 선택:
                # - 최소값을 총 비용에 더함
                # - pre 힙을 갱신
                # heapreplace: 현재 힙에서 최소값을 pop해서 res로 더하고
                # (pop 하면 삭제됨)
                # 새로운 값인 costs[i]를 추가
                res += heapreplace(pre, costs[i])  # 최소값을 대체
                i += 1  # pre 다음 인덱스로 이동
            else:
                # suf에서 최소값을 선택:
                # - 최소값을 총 비용에 더함
                # - suf 힙을 갱신
                res += heapreplace(suf, costs[j])  # 최소값을 대체
                j -= 1  # suf 이전 인덱스로 이동

        return res  # 최종 비용 반환

 

• 이해 겨우 했음.
• 그러나, 코드는 아직..

heapreplace의 동작

heapreplace(heap, item)는 Python의 heapq 라이브러리에서 제공하는 함수입니다.
이 함수는 다음 작업을 수행합니다:

1. 힙에서 최솟값 제거:
   • 현재 heap에서 최소값을 제거하고 반환합니다.
2. 새로운 값 추가:
   • 제거된 자리에 **새로운 값(item)**을 추가한 뒤, 힙의 상태를 유지합니다.

---

코드에서의 역할

1. 현재 힙의 최솟값을 선택

• 최소값을 반환하면서 동시에 제거합니다.
• 선택된 근로자의 비용을 총 비용(res)에 더합니다.

2. 새로운 후보를 추가

• costs[i](새로운 후보)를 힙에 추가합니다.
• 힙 상태가 유지되도록 최소 힙으로 재정렬됩니다.

 

heapreplace를 사용하는 이유

1. 효율성:
   • 힙에서 최소값을 반환하고 새로운 값을 추가하는 작업이 한 번에 수행됩니다.
   • 시간 복잡도: O(log⁡n)O(\log n)O(logn) (힙 재정렬).
2. 최소값 유지:
   • 힙은 항상 최소값을 유지하므로, 다음 세션에서도 가장 작은 비용을 쉽게 선택할 수 있습니다.

 

res += heapreplace(pre, costs[i])

 

• heapreplace의 역할:
  1. 힙에서 최솟값을 제거하고 반환 (즉, 선택된 근로자 비용 추가).
  2. 새로운 후보(costs[i])를 힙에 추가.
  3. 힙은 최소 힙으로 유지.
• 왜 사용하는가?
  heapreplace는 최소값 제거와 값 추가를 동시에 처리하므로 코드가 간결하고 효율적입니다.