[215. Kth Largest Element in an Array] (알고리즘)

Heap

문제

문제 링크

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2 Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

스스로 고민

접근법

• 정렬을 하지 않은 상태로 k 번째로 큰 요소를 반환하면 된다.
• 우선 파이썬 내장 함수를 이용하면 매우 간단하게 문제를 해결 할 수 있다.

class Solution:

    def findKthLargest(self, nums: List[int], k: int) -> int:

        nums.sort()

        return nums[-k]

• stack을 이용해서도 문제를 풀 수 있을 것 같은데 이번 주제가 heap 이였으니 힙에 대한 이해도 할 겸 힙으로 풀어보자

heapq ?!

heapq는 Python의 표준 라이브러리 모듈 중 하나로, 힙(Heap) 자료 구조와 관련된 함수와 클래스를 제공한다. heapq 모듈을 사용하면 최소 힙(Min Heap)과 최대 힙(Max Heap)을 구현하고 다룰 수 있으며, 데이터의 추가, 삭제, 힙 속성 유지 등을 간편하게 처리할 수 있다.

주요 함수와 클래스에는 다음과 같은 것들이 포함되어 있다:

1. heapify(iterable): 주어진 iterable 객체를 힙으로 변환한다. 리스트를 최소 힙 또는 최대 힙으로 변환할 수 있다.
2. heappush(heap, item): 힙에 요소를 추가한다. 요소는 힙 속성을 유지하면서 삽입된다.
3. heappop(heap): 힙에서 가장 작은(또는 가장 큰, 최대 힙의 경우) 요소를 제거하고 반환한다.
4. heapreplace(heap, item): 힙에서 가장 작은(또는 가장 큰) 요소를 제거한 다음 새로운 요소를 추가한다. heappush()와 heappop()의 조합과 같다.
5. nlargest(n, iterable): iterable에서 가장 큰 n개의 요소를 리스트로 반환한다.
6. nsmallest(n, iterable): iterable에서 가장 작은 n개의 요소를 리스트로 반환한다.
7. heapq 모듈은 기본적으로 최소 힙을 다루도록 설계되어 있으며, 최대 힙을 다루려면 요소를 음수로 바꿔서 활용할 수 있다.

heapq 모듈은 효율적인 데이터 처리를 위해 많이 사용되며, 우선순위 큐, 다익스트라 알고리즘, 정렬 알고리즘 등 다양한 알고리즘에서 활용한다.

의사코드

1. heap = nums[:k]: 초기에 heap은 배열 nums의 처음 k개 요소로 초기화된다.
2. heapify(heap): heapify() 함수를 사용하여 heap을 최대 힙으로 변환한다. 이 함수는 배열을 가져와 힙 속성을 유지하도록 재정렬한다. 따라서 heap[0]에는 현재 heap의 가장 큰 요소가 위치하게 된다.
3. for i in range(k, len(nums)):: 이제 k번째 요소부터 배열 nums의 끝까지 순회한다.
4. if heap[0] < nums[i]:: 현재 heap의 가장 큰 요소 (루트 요소)와 현재 요소 nums[i]를 비교한다.
5. heapreplace(heap, nums[i]): 만약 현재 요소 nums[i]가 더 크다면, heap[0] (현재 가장 큰 요소)를 nums[i]로 대체한다. 이 과정을 통해 heap은 항상 k개의 가장 큰 요소를 유지하며, k번째로 큰 요소가 heap[0]에 위치하게 된다.
6. return heap[0]: 배열 nums를 모두 순회한 후, heap[0]에는 k번째로 큰 요소가 저장되어 반환된다.

구현 코드

import heapq

def findKthLargest(nums, k):
	# Sorting
	# Time Complexity: O(nlogn)
	# Space Complexity: O(n)
	# nums.sort()
	# return nums[-k]
	
	# Heap
	# Time Complexity: O(k + (n-k)logk)
	# Space Complexity: O(k)
	heap = nums[:k]
	heapify(heap)
	for i in range(k, len(nums)):
		if heap[0] < nums[i]:
			heapreplace(heap, nums[i])
	return heap[0]

nums = [3,2,1,5,6,4]
k = 2

• 위와 같이 nums가 [3,2,1,5,6,4] K 는 2 라고 가정할 때 heap 은 [3,2] 가 된다.
• 이렇게 하는 이유는 초기 힙을 구성하기 위해서인데 이 힙을 유지하면서 k 번째로 큰 요소를 찾기 위해서다.
• 현재 최소힙이기 때문에 루트 노드가 항상 가장 작은 요소가 된다. k 번 째로 큰 요소를 찾기 위해서는 최소 힙이 적절하다.
• 현재 heap[0] 은 현재 힙에서 가장 작은 요소가 위치한다.
• 만약 heap[0] 가 nums[i] (현재 처리중인 요소) 와 비교했을 때 nums[i]가 더 크다면 heap[0] 를 nums[i] 로 대체한다.
• 이렇게 하면 heap은 항상 k 개의 가장 큰 요소를 유지할 수 있다.

그럼 heapq에서 최대힙은 어떻게 구하고 최소힙 구현과 뭐가 다를까?

import heapq

arr = [4, 10, 3, 5, 1]
print("Original array:", arr)

heapq.heapify(arr)  # 리스트를 최소 힙으로 변환
print("Min heap:", arr)

# 프린트문 
Original array: [4, 10, 3, 5, 1]
Min heap: [1, 4, 3, 5, 10]


# 리스트의 모든 요소에 음수를 곱해 최대 힙으로 변환
arr = [4, 10, 3, 5, 1]

max_heap = [-x for x in arr]
heapq.heapify(max_heap)

# 다시 음수를 취해 원래 값으로 복원
max_heap = [-x for x in max_heap]

print("Original array:", arr)
print("Max heap:", max_heap)

Original array: [4, 10, 3, 5, 1]
Max heap: [10, 5, 3, 4, 1]

시간 복잡도와 공간 복잡도

1. 정렬 (Sorting) 방식:

   • 시간 복잡도: O(nlogn) - 리스트를 정렬하는 데 O(nlogn) 시간이 걸린다.
   • 공간 복잡도: O(n) - 정렬된 리스트를 복제하므로 O(n) 공간이 필요하다.

2. 힙 (Heap) 방식:

   • 시간 복잡도: O(k + (n-k)logk)
     • 처음 k개의 요소를 힙에 삽입하는 데 O(k) 시간이 걸린다.
     • 나머지 (n-k)개의 요소에 대한 연산은 힙 크기인 k에 대해 logk 시간이 걸리므로 (n-k)logk 시간이 걸린다.
   • 공간 복잡도: O(k) - k개의 요소를 저장하기 위한 힙이 필요하다.

따라서 두 가지 접근 방식 모두 시간 복잡도는 O(nlogn) 이상이고, 공간 복잡도는 정렬 방식이 O(n)이고 힙 방식이 O(k)다. 일반적으로 k가 n보다 작은 경우에는 힙 방식이 정렬 방식보다 효율적이다. 하지만 k가 n에 가까운 경우에는 힙 방식의 시간 복잡도가 정렬 방식과 비슷해질 수 있다.

회고 과정

솔직히 100프로 이해가 가지 않는다. 라이브러리를 통해 문제를 풀기는 했지만 힙을 직접 구현하고 다음 문제로 넘어가야 될 것 같다.

힙 구현

• 힙은 보통 바이너리 힙을 가리키고 이때 최대 힙과 최소 힙이 있다.
• 조건
  • 1. 모든 부모가 자식 노드보다 크거나 같은 값
       • 혹은 모든 부모가 자식 노드보다 작거나 같은 값
       • 
       • 
  • 1. 완전 이진트리구조 -> 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고 마지막 레벨에서는 왼쪽부터 차례대로 채워져 있는 이진 트리를 말한다.
  • 
• 완전 이진 트리 -> 배열로 표현
• 
• 아래 특징 덕분에 트리의 노드 간 관계를 배열 인덱스를 통해 쉽게 파악하고 조작할 수 있다.
• 

출처- 자료정리 -

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_ = min(nums)
        max_ = max(nums)
        count = [0] * (max_ - min_ + 1)

        for num in nums:
            count[num - min_] += 1

        n = len(count) - 1
        while k > 0:
            k -= count[n]
            if k <= 0:
                return n + min_
            n -= 1
        return -1    

1. 먼저, 주어진 리스트 nums에서 최솟값(min_)과 최댓값(max_)을 찾는다.
2. 최솟값과 최댓값 사이의 모든 정수를 커버하기 위해 크기가 max_ - min_ + 1인 count 리스트를 생성한다. 이 리스트는 해당 숫자의 빈도수를 저장한다.
3. nums 리스트를 순회하면서 각 숫자를 min_을 빼고, 이를 인덱스로 사용하여 count 리스트에서 해당 숫자의 빈도수를 증가시킨다. 이렇게 하면 각 숫자가 몇 번 나왔는지를 기록하게 된다.
4. n 변수를 count 리스트의 길이에서 1을 뺀 값으로 초기화하고, k를 감소시키면서 반복한다. 이 반복문은 k가 0 이하가 될 때까지 실행된다.
5. 각 반복에서 현재의 n 인덱스에 해당하는 숫자의 빈도수를 k에서 빼면서 k를 업데이트한다. 만약 k가 0 이하가 되면, 현재의 n 값에 min_을 더한 것이 k번째로 큰 숫자다. 따라서 해당 값을 반환한다.
6. 반복문을 모두 실행한 후에도 k가 0 이하가 되지 않으면, 주어진 리스트에서 k번째로 큰 숫자를 찾을 수 없으므로 -1을 반환한다.

이 방법은 정렬이나 힙을 사용하지 않고 선형 시간 복잡도로 k번째로 큰 숫자를 찾는 방법이다. 빈도수를 계산하여 큰 숫자부터 순차적으로 확인하기 때문에 효율적이라고 생각한다.