728x90
정수 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() 호출마다 정렬이 필요하여 데이터가 많아지면 속도가 느려질 수 있다.
728x90
