[leetcode] 347. Top K Frequent Elements 파이썬 코드

이 문제는 제목에 그대로 나와있다. 숫자 배열이 주어지면 그 중에서 가장 빈번하게 (많이) 등장한 숫자를 반환하면 된다.

 

문제를 풀 때 숫자가 몇 번 나왔는지를 카운트하고 그것을 딕셔너리에 저장한 다음에 어떻게 해야 하는지 막혔다.

그래서 다른 사람들의 풀이를 보았다.

 

첫 번째, bucket sort.

숫자 배열이 주어지면 그 배열의 길이를 알 수 있다. 그리고 element가 아무리 많이 등장해도 (배열의 길이)번 만큼만 등장할 수 있다. 

그러면 개수를 key로, 그만큼 등장한 숫자를 value에서 배열로 저장하는 방법이 있다.

 

1이 몇 개, 2가 몇 개... 이렇게 개수(count)를 value로 두었는데 개수(count)를 key로 가져간다는 게 새로웠다.

count	0	1	2	3	...	K-2	K-1	K
		[3]		[1, 2]

 

간단하게 코드를 작성하면 다음과 같다.

# top k frequent elements
nums = [1,1,1,2,2,3]
bucket = [[] for i in range(len(nums)+1)] # [[], [], [], [], [], [], []]
num_count = dict()

print(bucket)

for i in range(len(nums)):
    if nums[i] in num_count:
        num_count[nums[i]] += 1
    else:
        num_count[nums[i]] = 1

print(num_count)

for value, count in num_count.items():
    bucket[count].append(value)

print(bucket)

 

 

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        bucket = [[] for i in range(len(nums)+1)] 
        num_count = dict()

        for i in range(len(nums)):
            if nums[i] in num_count:
                num_count[nums[i]] += 1
            else:
                num_count[nums[i]] = 1
        
        for value, count in num_count.items():
            bucket[count].append(value)

        result = []

        for idx in range(len(bucket)-1, 0, -1):
            for num in bucket[idx]:
                result.append(num)

                if len(result) == k:
                    return result

 

 

 

두 번째, heap

 

from collections import Counter
import heapq

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counter = Counter(nums)
        heap = []
        result = []
        for num, count in counter.items():
            if len(heap) < k:
                heapq.heappush(heap, (count, num))
            else:
                heapq.heappushpop(heap, (count, num))
        
        for tupl in heap:
            result.append(tupl[1])

        return result

 

 

참고

https://youtu.be/YPTqKIgVk-k?si=sSQkzs_FaC_FCuuN

https://youtu.be/phNDYf1xzco?si=LL7I13dM-xPP5HDl