[LeetCode 해석 및 풀이] 347. Top K Frequent Elements

LeetCode 문제 해석 및 풀이 방법

 

문제 347. Top K Frequent Elements (상위 k번째로 자주 나오는 원소들)

바로가기

 

문제 설명

영문

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

 

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

 

한글

정수 배열 nums와 정수 k가 주어졌을 때, 상위 k번째로 자주 나오는 원소들의 목록을 구하세요. 순서는 아무렇게나 제출해도 상관없습니다.

 

추가 : 알고리즘의 시간 복잡도는 O(n log n)보다 좋아야 합니다. (n은 배열의 크기)

 

제한조건

• 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.

 

입출력 예

입력	출력
nums = [1,1,1,2,2,3], k = 2	[1,2]
nums = [1], k = 1	[1]

 

해답 및 해설

파이썬 (Python)

O(n log n)보다 더 좋은 시간 복잡도를 가져야 하므로, 정렬은 통하지 않는다.

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

        for num in nums:
            num_dict[num] += 1
        
        frecuent_dict = defaultdict(list)

        for num, frec in num_dict.items():
            frecuent_dict[frec].append(num)

        result = []

        for freq_key in sorted(frecuent_dict.keys(), reverse=True):
            num_list = frecuent_dict[freq_key]

            result += num_list
            k -= len(num_list)
            if k == 0: break

        return result

 

우선 해당 숫자가 얼만큼 나오는지 횟수를 세어주고, 그 횟수에 따라 다시 숫자들을 묶어주었다. 그 후 횟수를 정렬해준 다음 가장 큰 횟수부터 차례대로 숫자를 빼주었다. 답이 유일하다 했으니 k 숫자가 딱 떨어지지 않는 경우는 생각하지 않았다.

 

이렇게 하게 된다면 시간 복잡도는 O(n) + O(aloga) (a는 횟수의 가짓수)가 되어 O(nlogn)보다는 빠르게 된다. (a의 최댓값은 대충 √2n인가?)

 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        x=Counter(nums)
    
        l=sorted(x,key=x.get,reverse=True)

        return l[:k]

위 풀이를 Counter라는 내장함수를 이용해서 푼 예시이다. 하지만 이 풀이는 시간 복잡도가 O(n) + O(blogb) (b는 각 숫자의 가짓수)가 된다.