[LeetCode | Python] 703. Kth Largest Element in a Stream

정수 k와 초기 스트림 nums가 주어질 때,

새로운 값이 추가될 때마다 K번째로 큰 값을 반환하는 클래스를 구현하는 문제다.

constructor는 클래스를 처음 생성할 때 실행되는 함수.

Python에서는 __init__()이 constructor(생성자) 역할을 한다. 

 

 

풀이1: Min-Heap 이용

이 문제의 가장 효율적인 풀이는 Min-Heap을 이용하는 것이다. 

import heapq
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.minHeap, self.k = nums, k
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap) # k개만 남기고 나머지 제거

    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap) # k개 유지
        return self.minHeap[0] # k번째로 큰 값 반환


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

최소 힙을 사용해 최대 k개의 원소만 유지하고,

새로운 값 추가 시 heappush(), k+1개가 되면 heappop()으로 가장 작은 값을 제거한다. 

힙 연산의 시간 복잡도는 heappush()와 heappop()의 시간 복잡도는 O(log n)이다.

KthLargest에서 add(val)을 호출 시 시간 복잡도는 O(log n)이며

m번 호출되면 O(m * log n)이 된다. 

 

 

 

풀이2: Sorting - O(m * n log n)

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.arr = nums

    def add(self, val: int) -> int:
        self.arr.append(val)
        self.arr.sort()
        return self.arr[len(self.arr) - self.k]

새로운 값을 리스트에 추가한 후 정렬하여 K번째로 큰 값을 반환. 

매번 정렬하므로, O(m * n log n)이 되며 

add() 호출마다 정렬이 필요하여 데이터가 많아지면 속도가 느려질 수 있다.