LeetCode [215]: Kth Largest Element in an Array

📌 LeetCode [215]: Kth Largest Element in an Array

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums와 정수 k가 주어질 때, 배열에서 k번째로 큰 요소를 반환하세요.
k번째로 큰 요소는 배열이 정렬되었을 때의 k번째 요소를 의미합니다.

---

문제 해결 접근 🧩

1. 최대 힙을 사용한 접근:
   • 모든 숫자를 -num 형태로 힙에 추가하여 최대 힙처럼 동작하도록 만듦.
   • 힙에서 k-1번 heappop으로 요소를 제거한 후, k번째로 큰 요소를 반환.
   • 시간 복잡도는 O(n + k log n).
2. 리팩토링 가능 여부:
   • 더 빠른 방법:
     • Python의 heapq.nsmallest를 사용하여 O(n + k log n)에서 불필요한 반복 제거 가능.
   • 효율적 접근:
     • nums.sort(reverse=True)를 사용해 정렬 후 nums[k-1]를 반환하면 O(n log n).

---

Solution 💻

원래 코드

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        q = []

        for num in nums:
            heapq.heappush(q, -num)
        
        for _ in range(k - 1):
            heapq.heappop(q)
        
        return -heapq.heappop(q)

시간 복잡도 ⏲️

• 힙 구성: O(n log n)
• 힙에서 k-1번 pop: O(k log n)
• 총 시간 복잡도: O(n + k log n).

공간 복잡도 🗄️

• 힙 크기: O(n).

---

리팩토링 🛠️

개선된 코드

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

리팩토링 후 시간 복잡도 ⏲️

• 힙 구성 및 추출: O(n log k)
• 총 시간 복잡도: O(n log k)

리팩토링 후 공간 복잡도 🗄️

• 힙 크기: O(k).