Top K Frequent Elements

Top K Frequent Elements :
https://neetcode.io/problems/top-k-elements-in-list/question

문제 파악

정수 배열 nums와 정수 k가 주어졌을 때, 배열 nums 에서 가장 많이 등장한 원소 k개

문제 핵심

빈도수가 높은 순서대로 상위 k개 반환하고, 정답은 항상 유일하다. 출력의 순서는 상관 없음

사고흐름

먼저 빈도수를 측정할 ADT로 Map (Dictionary) 선택
각 숫자와 등장 횟수를 매핑한다.
Map에서는 삽입과 조회가 평균 O(1)이기 때문에 적합함.
dictionary에서 가장 빈도수가 많은 value 값을 어떻게 효율적으로 추출해내냐 였는데 너무 생각이 안나서 그냥 max() 메소드를 사용해서 while 루프를 돌아서 해결함.
가장 형편없는 풀이로 시간 복잡도가 O(n^2) 까지 나옴

while k >0 루프에서 seen의 크기를 distinct elements = m으로 할 때
max()가 전체 순회해서 시간복잡도가 O(m)
이 방법을 k번 반복하고 있어서 O(kxm)
최악의 경우 모든 값이 다 다르면 m=n 으로 O(n^2)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        ans = []
        seen = {}
        
        for n in nums:
            if n not in seen:
                seen[n] =1
            else:
                seen[n] = seen.get(n,0)+1
                
        while k>0:
            max_key = max(seen, key=seen.get)
            ans.append(max_key)
            del seen[max_key]
            k-=1
            
        return ans

개선

Map(Dictionary)에서 빈도수를 체크하는 방법으로는 (1) 정렬 , (2) Heap, (3)Bucket 세 가지 방법이 있음

(1) 정렬

• HashMap으로 빈도를 계산한 다음에, (숫자, 빈도) 쌍을 리스트로 변환하고, 빈도 기준으로 내림차순 정렬해서 앞에서 k개를 선택하는 것
  이 때는 빈도 계산 O(n)과 정렬하는 O(mlogm, m=distinct element 개수)로 구현은 쉽지만 최적은 아님

from collection import Counter

def topKFrequent(nums, k):
	freq = Counter(nums)
    sorted_items = sorted(freq.item(), key= lambda x: x[1], reverse=True)
    return [num for num, _ in sorted_nums[:k]]

-> 빈도 계산 시간복잡도 O(n), 정렬 O(m log m, m= 서로 다른 원소 개수)
전체 시간 복잡도 O(n log n) (최악)

(2) Heap

• Priority Queue (우선순위큐)를 사용해서, 빈도가 높은 것부터 꺼내는 방법이 있음. 혹은 크기 k의 최소 힙을 유지하ㅡㄴ 것.

방법 A. Max Heap

• 빈도 Map 생성 -> (빈도, 숫자)를 Max Heap에 삽입해서, k번 pop 하는 것. 시간 복잡도는 O(n log n)

방법 B. Min Heap (더 최적)

• 빈도 Map 생성 -> Heap 크기를 k로 제한함. 빈도가 낮은 것부터 제거 해서 Heap에 남은 k개가 정답. 시간복잡도는 O(n log k)
  -> k가 작을 때는 효율적. Top-K 문제의 전형적인 해법

import heapq
from collections import Counter

def topKFrequent(nums, k):
	freq = Counter(nums)
    heap = []
    
    for num, count in freq.items():
    	heapq.heappush(heap, (count, num))
        if len(heap) > k:
        	heapq.heappop(heap)
            
   return [num for count, num in heap]

-> k가 작을 때 매우 효율적
Heap 연산 O(log k), 전체 시간복잡도 O(n log K)

import heapq

def topKFrequent(nums, k):
	count = {}
    for n in nums:
    	count[n] = count.get(n,0) +1
    
    return heapq.nlargest(k, count.keys(), key=count.get) 
    

(3) Bucket Sort

• 가장 최적의 풀이 방법으로, Map(빈도계산), 빈도의 배열을 저장하는 배열을 생성하는 것
• 빈도 Map 생성 후에 크기 n+1의 배열을 생성한다.
  index= 빈도, value = 해당 빈도의 숫자 리스트
• 빈도가 큰 index부터 내려가면서 k개를 수집함
  이러면 전체 시간 복잡도는 O(n)

from collection import Counter

def topKFrequent(nums,k):
	freq= Counter(nums)
    buckets = [[] for _ in range(len(freq)+1)]
    
    for num, count in freq.items():
    	buckets[count].append(num)
     
    ans = []
    for count in range(len(buckets)-1, 0, -1):
    	for num in bucket[count]:
        	ans.append(num)
            if len(ans) == k:
            	return ans
        

전체 시간복잡도 O(n)