[해시 테이블] 31 상위 K 빈도 요소(Top K Frequent Elements)

<LeetCode 문제>

https://leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode

<풀이>

collections.Counter를 이용하여 풀이한 첫번째 풀이는 다음과 같습니다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count_dict = collections.Counter(nums) #시간복잡도 O(N)
        count_list = list(count_dict.items()) #(key,value)형태로 list변환
        count_list.sort(key = lambda x: -x[1]) #등장빈도 내림차순 정렬
        
        return [count_list[i][0] for i in range(k)] #상위 k개만 리스트컴프리헨션으로

 

이때, Counter객체의 most_common()을 이용하여 풀이를 단순화시킬 수 있습니다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count_list = collections.Counter(nums).most_common(k) #원소들이 (key,value)인 list 반환
        return [key for key,value in count_list] #튜플에서 앞의 key만 리스트컴프리헨션으로

 

이때, zip() 함수를 통해 더 단순화가 가능하며, 반환값이 튜플이지만 리스트와 마찬가지로 Leetcode에서 정답으로 인정됩니다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return list(zip(*collections.Counter(nums).most_common(k)))[0]

 

zip()은 여러 시퀀스에서 동일한 인덱스의 아이템을 순서대로 추출하여 튜플로 만들어 주는 역할을 합니다.

파이썬2에서는 zip()의 결과로 바로 리스트가 반환됐지만, 파이선3+에서는 제너레이터를 반환합니다. 따라서 실제값을 추출하려면 list()로 한번 더 묶어줘야 합니다.

a = ['a1', 'a2']
b = ['b1', 'b2']
c = ['c1', 'c2']
d = ['d1', 'd2']
list(zip(a,b,c,d)) #[('a1','b1','c1','d1'), ('a2','b2','c2','d2')]

 

파이썬에서 아스테리스크 *는 시퀀스 언패킹 연산자로 시퀀스를 풀어헤칩니다.

fruits=['lemon', 'pear', 'watermelon', 'tomato']
print(*fruits) #lemon pear watermelon tomato

 

*가 함수의 파라미터가 되었을 때는 반대로 패킹도 가능합니다. 이는 파이썬3+에서 print()의 기본 동작 원리이기도 합니다.

def f(*params):
	print(params)
    
f('a','b','c') #('a','b','c')

 

변수 할당에서 *가 사용되면 나머지 모든 값을 의미하게 됩니다.

a,*b = [1,2,3,4]
a #1
b #[2,3,4]

*a,b = [1,2,3,4]
a #[1,2,3]
b #4

 

**는 키/값 페어를 언패킹하는데 사용됩니다.

date_info = {'year':'2020', 'month':'01', 'day':'7'}
new_info = {**date_info, 'day':'14'}
new_info #{'year':'2020', 'month':'01', 'day':'14'}

 

추가로 힙을 이용하여 문제를 풀이할 수도 있습니다. 파이썬 heapq 모듈은 Min heap만 지원하므로 키값을 음수로 넣어 Max heap처럼 이용합니다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = collections.Counter(nums)
        freqs_heap = []
        
        #Min heap에 음수로 삽입(max heap처럼 사용)
        for f in freqs:
            heapq.heappush(freqs_heap, (-freqs[f],f))
        
        topk = []
        #heap에서 k번 추출
        for _ in range(k):
            topk.append(heapq.heappop(freqs_heap)[1])
        
        return topk

 

heapq 모듈 사용법은 다음 링크에서 자세하게 확인할 수 있습니다.

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

<학습내용>

1. zip()을 통해 여러 시퀀스를 같은 인덱스끼리 튜플로 묶기
2. 아스테리스크(*)의 다양한 쓰임새

<학습이 필요한 내용>

1. heapq 사용법
2. dictionary가 hash기반인데 for문이 되는 이유(링크)
3. 형변환할때의 시간복잡도 정리