[Leetcode] 347. Top K Frequent Elements_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '347. Top K Frequent Elements'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Top K Frequent Elements' 알고리즘 문제

 

STEP 2. 'Top K Frequent Elements' 코드(code)

 

STEP 3. 'Top K Frequent Elements' 해설

 

STEP 4. 'Top K Frequent Elements' solution

 

반응형

 

STEP 1. 'Top K Frequent Elements' 알고리즘 문제

 

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

정수 배열 nums와 정수 k가 주어지면 가장 자주 사용되는 k개의 요소를 반환합니다. 어떤 순서로든 답변을 반환할 수 있습니다.

 

Constraints:

 

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

 

---

STEP 2. 'Top K Frequent Elements' 코드(code)

 

■ Runtime: 90 ms Beats 50.15% of users with Python3
■ Memory: 21.05 MB Beats 70.75% of users with Python3

 

from operator import itemgetter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count_dict = dict()

        for n in nums:
            if n not in count_dict:
                count_dict[n] = 1
            else :
                count_dict[n] += 1
        topKdict = dict(sorted(count_dict.items(), key = itemgetter(1), reverse=True)[:k])
        return list(topKdict.keys())

---

STEP 3. 'Top K Frequent Elements' 해설

 

Hash 및 Array 방식을 활용하여, 처음 나오는 값은 Dictionary에 추가하면서 횟수 1을 적용합니다. 그리고 동일한 값이 나오면 dictionary을 업데이트하면서 + 1을 합니다.

 

그리고 최종적으로 value값을 기준으로 내림차순으로 정렬하기 위해, itemgetter(1) (만약에 key를 기준으로 한다면, itemgetter(0)으로 적용하면 됩니다)과 reverse=True로 설정합니다. 최솟값 k개를 가져오기 위해, list의 범위를 지정해 줍니다. 그리고 key를 출력해줘야 하기에 dict 함수로 dictionary로 변환합니다.

 

만약에 dictionary 변환하지 않으면, [(key1, value1), (key2, value2), .... , (keyN, valueN)] 형태로 List[Tuple(Key, value)] 값으로 계산됩니다. 그리고 최종적으로 key를 list에 저장해서 return 합니다.

 

 

STEP 4. 'Top K Frequent Elements' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 84 ms Beats 80.35% of users with Python3
■ Memory: 20.63 MB Beats 98.29% of users with Python3

 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # find the frequency of each number
        num_frequency_map = {}
        for num in nums:
            num_frequency_map[num] = num_frequency_map.get(num, 0) + 1
        top_k_elements = []

        # go through all numbers of the num_frequency_map
        # and push them in the top_k_elements, which will have
        # top k frequent numbers. If the heap size is more than k,
        # we remove the smallest(top) number
        for num, frequency in num_frequency_map.items():
            heappush(top_k_elements, (frequency, num))
            if len(top_k_elements) > k:
                heappop(top_k_elements)

        # create a list of top k numbers
        top_numbers = []
        while top_k_elements:
            top_numbers.append(heappop(top_k_elements)[1])

        return top_numbers

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '347. Top K Frequent Elements'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.