[해시 테이블] 상위 K 빈도 요소

347  | Top K Frequent Elements
https://leetcode.com/problems/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.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

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.

 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

 

 

 

작성 코드

 

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        answer = []
        count_num_order = sorted(Counter(nums).items(), key = lambda item : item[1], reverse = True)
        for i in range(k):
            answer.append(count_num_order[i][0])
        return answer

 

• 1년 전에 풀었던 문제인데 당시에는 못 풀고 답지를 참고했었음
• Counter 객체를 이용하여 각 원소 별 개수 count -> 원소1 : 원소1의 개수, 원소2 : 원소 2의 개수
• 개수에 따른 정렬이 필요하여 lambda 사용 item[1], 즉 개수에 따른 내림차순 정렬 시행
• 반복문 k 만큼만 돌면 됨

 

 

참고 코드

 

생각보다 엄청 기발한 코드가 없어서 이전 작성한 글의 참고 코드 가져옴 (책에 있던 코드)

 

https://dawngreen.tistory.com/99

[해시 테이블] 상위 K 빈도 요소

 

 

회고

 

• 이 문제가 해시 챕터에 있어서 해시로 풀이하려고 했는데 어떻게 하나 싶었음
• 생각해보니 Counter 안 썼으면 defaultdict 만들어주고 해시 썼을 것 같