p. 307: 31. 상위 K 빈도 요소 - 최적화 & 파이써닉한 코드 질문 #164
Description
안녕하세요,
307쪽 31번 문제(상위 K 빈도 요소)에서 힙과 Counter() 객체를 활용한 풀이 2개에 대해 질문 몇 개를 여쭤보고자 합니다.
질문 1 - O(n log n) 시간 복잡도 풀이를 O(n log k)로 최적화하는 것이 의미가 있을까요?
책에 수록된, 최대힙을 활용한 풀이
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freqs = collections.Counter(nums) # O(n) 시간 & O(n) 공간 (여기서 `n`은 len(nums))
freqs_heap = []
for f in freqs:
heapq.heappush(freqs_heap, (-freqs[f], f)) # `freq_heap`: O(n log n) 시간 & O(n) 공간
topk = list()
for _ in range(k):
# 아웃풋 리스트인 `topk`를 공간 복잡도 계산에 고려하지 않았을 때, O(k log n) 시간 & O(1) 공간
topk.append(heapq.heappop(freqs_heap)[1])
return topk이 풀이에서 Counter() 객체의 값을 음수화하여 (-freqs[f]) 힙에 삽입함으로써 최대힙을 구현하는데, n이 len(nums)라면, 이 풀이의 경우 시간 복잡도가 O(n log n), 공간 복잡도가 O(n)인 것을 볼 수 있습니다.
사소한 최적화이지만 최소힙을 활용하면 시간 복잡도를 O(n log k)로 줄일 수 있을 것 같은데, 이러한 최적화가 의미가 있을까요? "의미있음"은 주관적인 개념이긴 하지만, "면접 상황에서 이러한 최적화가 도움이 될까" 정도로 보시면 될 것 같습니다.
# 제 풀이
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# ⭐ 최적화 방법 1: n == k일 경우 바로 `nums`를 리턴함으로써 k < n을 보장 (여기서 `n`은 len(nums))
if len(nums) == k:
return nums
min_heap = [] # ⭐ 최적화 방법 2: 최대힙 대신 최소힙 사용하기
nums_to_counts = Counter(nums) # O(n) 시간 & O(n) 공간
for num, count in nums_to_counts.items(): # O(n log k) 시간 & O(k) 공간
heappush(min_heap, (count, num))
# 최소힙의 길이(혹은 사이즈)가 `k`를 넘어가면, 루트(최솟값)를 pop하면서 마지막에 상위 K 빈도 요소만 남겨둠
# min_heap의 공간 복잡도는 O(k)지만 위 Counter() 객체 때문에 풀이의 공간 복잡도는 결론적으로 O(n)
if len(min_heap) > k:
heappop(min_heap)
return [num for _, num in min_heap] # 공간 복잡도 계산 시 고려 X질문 2 - 더 간결하고, 파이써닉한 풀이
책에 있는 파이썬다운 풀이
def topKFrequent(self, nums, k):
return list(zip(*collections.Counter(nums).most_common(k)))[0]이거는 딱히 질문이라기보다는, 이 풀이가 CP스러운 것 같아서 언패킹을 활용하지 않고도 이렇게 더 간결하게 쓸 수 있을 것 같아요.
👇
# 제 풀이
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
return [num for num, _ in Counter(nums).most_common(k)] # O(n log n) 시간 & O(n) 공간읽어주셔서 감사합니다!
Reactions are currently unavailable