347. Top K Frequent Elements

가장 빈도가 잦은 숫자를 K순위까지 뽑는 문제이다.

Solution

1. 딕셔너리를 사용해 각 숫자의 개수를 저장한다.
2. 딕셔너리를 value 값을 기준으로 내림차순 정렬한다.
3. k번째 값까지 꺼내온다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = {}
        for i in range(len(nums)): # O(n)
            if nums[i] not in d: d[nums[i]] = 0
            d[nums[i]] += 1
        d = sorted(d.items(), key = lambda item: item[1], reverse = True) # O(nlogn)
        nums[:] = []
        for i in range(k): nums.append(d[i][0])
        return nums

시간 복잡도

1. 딕셔너리에 숫자를 저장하는 과정에서 O(n)
2. sorted() 함수를 사용할 때 O(nlogn)
3. k위 까지 꺼내는 반복문 O(k)

총 시간 복잡도는 O(nlogn) 이다.