[4코3파] # 279. LeetCode 215. Kth Largest Element in an Array (update)

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (279일차)
[4코1파] 2023.01.13~ (271일차)
[4코3파] 2023.10.01 ~ (9일차)

Today :

2023.10.09 [279일차]

215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

문제 설명

정렬 되어 있지 않은 정수 배열 nums가 주어졌을 때, k번째 큰 수를 return 한다.
k번째로 큰 수를 찾을 때는 배열을 정렬하지 않고, 선형 시간으로 해결해야 한다.

문제 풀이 방법

https://velog.io/@heyggun/1스4코2파-236.-LeetCode-215.-Kth-Largest-Element-in-an-Array

처음에는 주어진 배열을 모두 min Heap으로 만들어서
가볍게 k를 줄여가면서 pop 해도 맞는 문제 였다.
heapq.heapify(nums)를 사용하여 주어진 배열 nums를 최소 힙으로 변환하는데 O(N log(N))으로, 배열에서 가장 작은 요소를 K번 제거하면서 K번 반복하므로 O(K log(N))이 걸려서
총 시간복잡도를 O(N * log(N)) 로 풀었다. 여기서 공간복잡도는 O(k)

그래서 왜 이게 easy 가 아니라 medium 이여... 했었는데
조금 더 최적화해서 시간복잡도를 O(n*log(k))로 푸는 방법은
배열의 처음부터 k번째까지 즉, k개 요소가 담긴 최소 힙을 만든 후에,
배열 k번째 부터 배열의 요소와 최소 힙의 루트 노드의 원소와 비교하면서 업데이트 해가면 된다.
여기서의 공간복잡도 또한 O(k) 이다.

O(n)으로 푸는 quick sort를 활용한 neetcode 방법은 아직 이해를 못했다.
피봇어쩌구저쩌구 하는데 잘 모르겠음 ;;

내 코드

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        minHeap = nums[:k]
        heapq.heapify(minHeap)
        
        for num in nums:
            if num > minHeap[0]:
                heapq.heappop(minHeap)
                heapq.heappush(minHeap, num)
        
        return minHeap[0]

증빙

여담

quick sort 공부를 해야할 것 같다.