LeetCode [1046]: Last Stone Weight

📌 LeetCode [1046]: Last Stone Weight

🔗 문제 링크

---

문제 설명 📄

최대 힙을 사용하여 주어진 돌들의 무게를 비교하고, 가장 무거운 두 돌을 충돌시켜 결과를 계산합니다.

• 돌들의 무게 리스트 stones가 주어집니다.
• 각 반복마다 가장 무거운 두 돌을 선택하여 충돌시킵니다:
  • 두 돌의 무게가 같다면 두 돌 모두 소멸합니다.
  • 두 돌의 무게가 다르다면, 더 큰 무게에서 작은 무게를 뺀 결과가 남습니다.
• 더 이상 충돌할 돌이 없을 때, 남은 돌의 무게를 반환합니다. 만약 남아있는 돌이 없다면 0을 반환합니다.

---

문제 해결 접근 ✨

1. 최대 힙을 사용하여 가장 큰 두 돌을 효율적으로 추출:
   • heapq는 기본적으로 최소 힙을 지원하므로, 돌의 무게를 음수로 변환하여 최대 힙처럼 작동하게 만듭니다.
2. 반복적으로 두 돌을 꺼내 계산:
   • 가장 큰 두 돌의 차를 계산하고, 결과를 다시 힙에 삽입합니다.
3. 종료 조건:
   • 힙에 돌이 하나 남아있다면 해당 돌의 무게를 반환합니다.
   • 힙이 비었다면 0을 반환합니다.

---

Solution 💻

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        q = [-stone for stone in stones]
        heapq.heapify(q)

        while q:
            if len(q) < 2:
                return -q[0]

            y = -heapq.heappop(q)
            x = -heapq.heappop(q)

            if x != y:
                heapq.heappush(q, -(y - x))

        return 0

---

시간 복잡도 분석 ⏲️

• 힙 초기화: heapify의 시간 복잡도는 (O(n))입니다.
• 힙 연산: 돌의 수를 (n)이라고 할 때, 매번 최대값 두 개를 꺼내고 삽입하는 연산은 총 (O(log n))의 비용이 듭니다.
  • 최대 (n - 1)번의 충돌이 가능하므로, 최악의 경우 (O(n log n))의 시간 복잡도를 가집니다.
• 총 시간 복잡도: (O(n + n log n) = O(n log n)).

공간 복잡도 분석 🗄️

• 힙 저장 공간: 입력 돌의 개수 (n)만큼의 공간이 필요합니다.
• 총 공간 복잡도: (O(n)).

---